CareerCup4.1.cpp

CareerCup4.1.cpp

/*
 * Chapter 4
 * 4.1 Implement a function to check if a binary tree is balanced.
 * For the purposes of this question, a balanced tree is defined to
 * be a tree such that the heights of the two subtrees of any node
 * never differ by more than one.
 */

#include <iostream>
#include <cmath>  // for fmax(), fdim()

using namespace std;

typedef struct tree_node {
    int value;
    struct tree_node* left;
    struct tree_node* right;
    tree_node();
} tree_node;

tree_node::tree_node() {
    value = 5;
    left = NULL;
    right = NULL;
}
// recursively calculate tree height
int height(tree_node* root)
{
    if (root == NULL)
        return 0;
    else
        return fmax(height(root->left), height(root->right)) + 1;
}
// difference > 1 will be unbalanced
bool isBalanced(tree_node* root)
{
    if (fdim(height(root->left), height(root->right)) <= 1)
        return true;
    else
        return false;
}

int main(int argc, char const *argv[])
{
    tree_node* root = new tree_node;
    tree_node* p = root;
    // generate a un-balanced tree: left_height 2, right_height 0
    for (int i = 0; i < 2; ++i)
    {
        tree_node* node = new tree_node;
        p->left = node;
        p = node;
    }
    cout << isBalanced(root) << endl;  // 0 is unbalanced, 1 is balanced
    return 0;
}