Given a binary tree, write an efficient algorithm to check if tree is height balanced or not. In a height balanced tree, the absolute difference between height of left subtree and right subtree for every node is 0 or 1.

Simple solution would be to calculate the height of left subtree and right subtree for each node in the tree. If for any node, the absolute difference between the height of its left and right subtree is more than 1, the tree is unbalanced. The time complexity of this solution is **O(N ^{2}) **as there are N nodes in the tree and for every node we are calculating height of its left subtree and right subtree that takes O(N) time.

We can solve this problem in **linear time** by doing post-order traversal of the tree. Instead of calculating height of left subtree and right subtree for every node in the tree, we can get the height in constant time. The idea is to start from the bottom of the tree and return height of subtree rooted at given node to its parent node. The height of subtree rooted at any node is equal to 1 plus maximum height of the left subtree or right subtree.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Recursive function to check if given binary tree is height balanced or not int isHeightBalanced(Node* root, bool& isBalanced) { // base case: tree is empty or tree is not balanced if (root == nullptr || !isBalanced) return 0; // get height of left subtree int left_height = isHeightBalanced(root->left, isBalanced); // get height of right subtree int right_height = isHeightBalanced(root->right, isBalanced); // tree is unbalanced if absolute difference between height of // its left subtree and right subtree is more than 1 if (abs(left_height - right_height) > 1) isBalanced = false; // return height of subtree rooted at current node return max(left_height, right_height) + 1; } // Main function to check if given binary tree is height balanced or not bool isHeightBalanced(Node* root) { bool isBalanced = true; isHeightBalanced(root, isBalanced); return isBalanced; } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Very nice. You can optimize this even further by checking if isBalanced is false at the very beginning of the method. If it is, just return 0 (or anything), as you don’t need to calculate anything else if you’ve discovered another subtree is not balanced.

Thanks a lot for suggesting this optimization. We have updated the code. Happy coding 🙂