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);
}

Answer 1

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