# Check If a Given Tree is Height-balanced or Not

In this article, we are going to discuss **what a height-balanced tree is and how to find whether a tree is height-balanced or not?**

Submitted by Radib Kar, on August 08, 2020

## What is a height-balanced tree?

A tree is said to be height-balanced if the difference b/w its left subtree height and right subtree height is at most 1.

So, from the below example you can get an idea of which one is a height-balanced tree and which one is not. For checking height balancing, we use a term called ** balance factor**. Each node has a balance factor which is different b/w height of its subtrees.

Balance factor: abs(left subtree height – right subtree height)

Now,

For a tree to be a height-balanced tree, the balance factor of all node in the tree needs to be <=1

For the below example,

We have shown the trees with balance a factor labeled against each node.

**Example 1:**

In the above tree, we can see that for any node the balance factor is at most 1. Thus the above tree is **height-balanced**.

**Example 2:**

In the above tree, we can see that for the root node the balance factor is 2 which violates the property of the height-balanced tree. Thus the above tree is not **height-balanced**.

So how can we check whether a tree is height-balanced or not?

So, the idea is to check the balance factor for the root. If the balance factor for the root is less than or equal to 1 then we should check whether its subtrees are both height-balanced or not. If all these conditions satisfy then the tree is height-balanced otherwise not. So, In simple recursive definition,

Bool isBalanced(root){ If left subtree height and right subtree height has an absolute difference more than 1 then return false Return isBalanced(root->left) && isBalanced(root->right) }

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; // tree node is defined class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int data) { val = data; left = NULL; right = NULL; } }; int height(TreeNode* root) { if (!root) return 0; return 1 + max(height(root->left), height(root->right)); } bool isBalanced(TreeNode* root) { if (!root) return true; //balancefactor=diff b/w left subtree height //and right subtree height int balancefactor = abs(height(root->left) - height(root->right)); //if balance factor of current node >1 //then it can't be height-balanced if (balancefactor > 1) return false; //else if both subtrees are height //balanced then it's height-balanced too return isBalanced(root->left) && isBalanced(root->right); } int main() { //building the tree like example 1 TreeNode* root1 = new TreeNode(1); root1->left = new TreeNode(2); root1->right = new TreeNode(3); root1->left->left = new TreeNode(4); if (isBalanced(root1)) cout << "Tree in example 1 is height-balanced\n"; else cout << "Tree in example 1 is not height-balanced\n"; //building the tree-like example 2 TreeNode* root2 = new TreeNode(1); root2->left = new TreeNode(2); root2->right = new TreeNode(3); root2->right->left = new TreeNode(4); root2->right->left = new TreeNode(5); root2->right->left->left = new TreeNode(6); if (isBalanced(root2)) cout << "Tree in example 2 is height-balanced\n"; else cout << "Tree in example 2 is not height-balanced\n"; return 0; }

**Output:**

Tree in example 1 is height-balanced Tree in example 2 is not height-balanced

The time complexity of the above implementation is **O(n^2)** as it will keep computing height for each recursive call. That's what we can do instead of computing the height every time, we can store the height of each node in one iteration which will take **O(n)**. And then we will check recursively without computing the height in each recursive call, rather can find height from the loop up table in which we stored.

Below is the implementation where we have to create a hash table to store the height of each node so that height can be retrieved in **O(1)** time from the hash table. Below is the efficient implementation which solves in **O(2n)** time.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; // tree node is defined class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int data) { val = data; left = NULL; right = NULL; } }; int height(TreeNode* root, unordered_map<TreeNode*, int>& mymap) { //base case if (!root) return 0; //if height already calculated for the node return the height if (mymap.find(root) != mymap.end()) return mymap[root]; //calculate height int h = 1 + max(height(root->left, mymap), height(root->right, mymap)); //store in the hash table mymap[root] = h; return h; } bool isBalancedRecur(TreeNode* root, unordered_map<TreeNode*, int>& mymap) { if (!root) return true; //balancefactor=diff b/w left subtree height //and right subtree height //heights already stored in mymap int balancefactor = abs(mymap[root->left] - mymap[root->right]); //if balance factor of current node >1 //then it can't be height-balanced if (balancefactor > 1) return false; //else if both subtrees are height balanced //then it's height-balanced too return isBalancedRecur(root->left, mymap) && isBalancedRecur(root->right, mymap); } bool isBalanced(TreeNode* root) { unordered_map<TreeNode*, int> mymap; if (!root) return true; height(root, mymap); return isBalancedRecur(root, mymap); } int main() { //building the tree like example 1 TreeNode* root1 = new TreeNode(1); root1->left = new TreeNode(2); root1->right = new TreeNode(3); root1->left->left = new TreeNode(4); if (isBalanced(root1)) cout << "Tree in example 1 is height-balanced\n"; else cout << "Tree in example 1 is not height-balanced\n"; //building the tree-like example 2 TreeNode* root2 = new TreeNode(1); root2->left = new TreeNode(2); root2->right = new TreeNode(3); root2->right->left = new TreeNode(4); root2->right->left = new TreeNode(5); root2->right->left->left = new TreeNode(6); if (isBalanced(root2)) cout << "Tree in example 2 is height-balanced\n"; else cout << "Tree in example 2 is not height-balanced\n"; return 0; }

**Output:**

Tree in example 1 is height-balanced Tree in example 2 is not height-balanced

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.