Checking if a binary tree is balanced

Question

I implemented the C++ piece of code below, to check if a binary tree is balanced, i.e. the height of the left and right subtrees differ by at most 1. However, I am not sure if it is efficient, or repeatedly checks subtrees in a bad way. Can someone guide me please?

 unordered_map <Node*, int>  height;
    struct Node{
       int key;
       Node* left;
       Node* right;
    }
    bool isBalanced(Node* root){
        if (root == nullptr){
             height[root] = -1;
            return true;
        }
        if (!isBalanced(root->left)) return false;
        if (!isBalanced(root->right)) return false;

        height[root] = max(height[root->left], height[root->right]) + 1;


        return (abs(height[root->left] - height[root->right]) < 1);
}

You can make isBalanced to return int, -1 for unbalanced or depth otherwise. Then you do not need additional map — Slava
There is a lot of balanced trees, precise what you mean by balanced. Whatever, you should return height and compare heights of left and right subtrees. — Jean-Baptiste Yunès
@user25004 If you are sure that your code is actually working and you're asking for improvement, ask at SE Code Review please, providing the complete code. — πάντα ῥεῖ

Rafael Rafael · Accepted Answer · 2016-02-23T20:07:41

I will try to pass the idea using pseudo-code.

int CheckTreeHeight(Node root)
{
  if(root == null) return 0; // Height of 0.

  // Check if left is balanaced
  int leftChildHeight = CheckTreeHeight(root.left);
  if(leftChildHeight == -1) return -1; // Not Balanced

  // Check if right is balanaced
  int rightChildHeight = CheckTreeHeight(root.right);
  if(rightChildHeight == -1) return -1; // Not Balanced

  // Check if current node is balanced
  int heightDifference = leftChildHeight - rightChildHeight;

  if(Math.abs(heightDifference) > 1)
   return -1; // not balanaced
  else
   return Math.max(leftChildHeight, rightChildHeight) + 1; // Return Height
}

bool IsBalanced(Node root)
{
   if(CheckTreeHeight(root) == -1)
   {
      return false;
   }
   else
   {
      return true;
   }
}

This algorithm performs in O(n) time complexity and O(H) space complexity, where h is the height of the tree.

As mentioned by the algorithm's author, the idea is that we inspect the children of the root (that is left and right) recursively until we found unbalanced one, where we return -1.

With this technique, we return immediately if any of the sub-trees are unbalanced.

More information about this implementation you can find in the book mentioned in the reference bellow.

Reference
Cracking the Coding Interview 6th Edition

Checking if a binary tree is balanced

1 Answers