Balanced Tree detection

Implement a algorithm to check if a tree is balanced, given its root node. i.e. "no two leaf nodes should differ in distance from the root by more than one". use the function prototype- bool IsBalanced(node *root)

             3
           /  \
          8    8
         / \   /
        5   5 7

Answer:


Solution 1:
Using Level Order traversal,

bool IsBalanced(Node *root)
{
    Queue q;
    size_t prev_depth = 0;
    // We add the node, and the depth at which it
    // occurs
    q.enqueue( make_pair(root,0) );
    while ( !q.isempty() )
    {
        pair node_depth_info = q.dequque();
        Node* node = node_depth_info.first;
        size_t cur_node_depth = node_depth_info.second;
        if ( !node->left && !node->right )
        {
            // leaf!
            if (prev_leaf_depth != cur_node_depth)
            {
                // previous leaf depth is not same as the current one
                return false;
            }
            prev_leaf_depth = cur_node_depth;
        }
        // Add the children 
        if ( node->left )
            q.enqueue( make_pair(node->left, cur_node_depth + 1) );
        if ( node->right)
            q.enqueue( make_pair(node->right, cur_node_depth + 1) );
    }
    return true; // hurray!
}

Solution 2:

Do a traversal, pass the depth of prev tree node and current depth info to next traversal

bool __isBalanced(Node *root, size_t &prev_tree_depth, size_t &cur_depth)
{
    if ( root )
    {
        if ( !root->left && !root->right )
        {
            bool isLeftBalanced, isRightBalanced;
            if(!prev_tree_depth) prev_tree_depth = cur_depth; // first time init
            else
            {
                if (cur_depth != prev_tree_depth) return false; // does not match
                prev_tree_depth = cur_depth; // update
            }
        }
        cur_depth += 1;
        isLeftBalanced = __isBalanced(root->left, prev_tree_depth, cur_depth);
        if ( isLeftBalanced )
            isRightBalanced = __isBalanced(root->right, prev_tree_depth, cur_depth);
        else
            return false;
        return isLeftBalanced && isRightBalanced;
    }
    return true;
}

bool isBalanced(Node *root)
{
    size_t prev_tree_depth = 0, cur_depth = 1;
    return __isBalanced(root, prev_tree_depth, cur_depth );
}