Check If a Binary Tree Is Height-Balanced

80.5k
0

Given the root of a binary tree, determine whether it is height-balanced.

A binary tree is height-balanced if, for every node, the absolute difference between the heights of its left and right subtrees is at most 1.

In other words, for every node:

|leftHeight - rightHeight| <= 1

If even one node violates this condition, the entire tree is considered unbalanced.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]

Output: true

Explanation: The left subtree has height 1 and the right subtree has height 2. Their difference is 1, and every other node also satisfies the balance condition.

Example 2

Input: root = [1, 2, 2, 3, 3, null, null, 4, 4]

Output: false

Explanation: At one of the nodes, the left subtree becomes more than one level deeper than the right subtree. Since the height difference exceeds 1, the tree is not height-balanced.

Example 3

Input: root = []

Output: true

Explanation: An empty tree contains no node that can violate the balance condition, so it is considered height-balanced.

Approach 1

The balance condition must be verified at every node.

For the current node, first calculate the heights of its left and right subtrees. If their difference is greater than 1, the tree is immediately unbalanced.

Even if the current node satisfies the condition, the same check must still be performed inside both subtrees because an imbalance may exist deeper in the tree.

The drawback is that subtree heights are calculated repeatedly for different ancestors, creating unnecessary work.

Algorithm

  • If root is null, return true because an empty tree is balanced.

  • Use a helper function height that returns the height of a subtree.

  • Calculate leftHeight and rightHeight for the current node.

  • If abs(leftHeight - rightHeight) > 1, return false because the current node violates the balance condition.

  • Recursively verify that both the left and right subtrees are balanced.

  • Return true only if the current node and both subtrees satisfy the condition.

Dry Run

Balanced Binary Tree Approach 1 Dry Run.png

Balanced Binary Tree Approach 1 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
private:
/*
* Return the height of a subtree so the balance
* condition can be checked at the current node.
*/
int height(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return 1 + max(
height(root->left),
height(root->right)
);
}
public:
bool isBalanced(TreeNode* root) {
if (root == nullptr) {
return true;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
// A difference greater than one breaks the balance condition.
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
/*
* The condition must also hold at every node
* inside both subtrees.
*/
return isBalanced(root->left) &&
isBalanced(root->right);
}
};
int main() {
/*
1
/ \
2 2
/ \
3 3
/
4
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->right->right = new TreeNode(3);
root->left->left->left = new TreeNode(4);
Solution solution;
cout << (solution.isBalanced(root) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × H), where N is the number of nodes in the binary tree and H is the height of the tree. Subtree heights may be recalculated for multiple ancestors. This becomes O(N²) for a skewed tree and O(N log N) for a balanced tree.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Approach 2

The Approach 1 performs two related tasks separately:

  • calculate subtree heights,

  • check whether those subtrees are balanced.

Both can instead be handled during the same post-order traversal.

For every node, first obtain the heights of its left and right subtrees. If either subtree is already unbalanced, return a special value -1 immediately.

Otherwise, check the current height difference. If it exceeds 1, return -1; if not, return the normal subtree height.

This works because valid subtree heights are always 0 or greater, so -1 can safely represent an unbalanced subtree.

Algorithm

  • Create a helper checkHeight that returns the subtree height when balanced and -1 when unbalanced.

  • If the current node is null, return 0 because an empty subtree has height zero.

  • Compute leftHeight; if it is -1, return -1 immediately because the left subtree is already unbalanced.

  • Compute rightHeight; if it is -1, return -1 for the same reason.

  • If abs(leftHeight - rightHeight) > 1, return -1; otherwise return 1 + max(leftHeight, rightHeight).

  • The complete tree is balanced only if checkHeight(root) != -1.

Dry Run

Balanced Binary Tree Approach 2 Dry Run.png

Balanced Binary Tree Approach 2 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
private:
/*
* Return subtree height when balanced.
* Return -1 as soon as an imbalance is detected.
*/
int checkHeight(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = checkHeight(root->left);
// Propagate an already detected imbalance upward.
if (leftHeight == -1) {
return -1;
}
int rightHeight = checkHeight(root->right);
if (rightHeight == -1) {
return -1;
}
// The current node fails if its subtree heights differ too much.
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + max(leftHeight, rightHeight);
}
public:
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
};
int main() {
/*
1
/ \
2 2
/ \
3 3
/
4
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->right->right = new TreeNode(3);
root->left->left->left = new TreeNode(4);
Solution solution;
cout << (solution.isBalanced(root) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is processed at most once, and its height is calculated during the same traversal.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Approach 3

The Optimized DFS works in post-order because the height of a node can be determined only after the heights of its children are known.

The same order can be reproduced without recursion by using a stack. Each stack entry stores a node together with a flag indicating whether its children have already been processed.

Once a node is processed after its children, their heights are available in a map. Those heights are used to check the balance condition and calculate the current node's height.

This avoids recursion but requires additional storage for the height of processed nodes.

Algorithm

  • If root is null, return true.

  • Use a stack containing (node, visited) pairs and a map heightMap to store computed subtree heights.

  • When a node is first encountered, push it back with visited = true, then push its children so they are processed first.

  • When the node is popped with visited = true, obtain its left and right heights from heightMap, using 0 for missing children.

  • If their difference exceeds 1, return false; otherwise store 1 + max(leftHeight, rightHeight) as the current node's height.

  • If every node is processed without finding a violation, return true.

Dry Run

Balanced Binary Tree Approach 3 Dry Run.png

Balanced Binary Tree Approach 3 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (root == nullptr) {
return true;
}
/*
* The visited flag ensures children are processed
* before their parent, reproducing postorder traversal.
*/
stack<pair<TreeNode*, bool>> nodesStack;
nodesStack.push({root, false});
unordered_map<TreeNode*, int> heightMap;
while (!nodesStack.empty()) {
auto [node, visited] = nodesStack.top();
nodesStack.pop();
if (!visited) {
nodesStack.push({node, true});
if (node->right != nullptr) {
nodesStack.push({node->right, false});
}
if (node->left != nullptr) {
nodesStack.push({node->left, false});
}
} else {
/*
* Child heights are already available because
* the node is processed only after its children.
*/
int leftHeight = node->left
? heightMap[node->left]
: 0;
int rightHeight = node->right
? heightMap[node->right]
: 0;
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
heightMap[node] =
1 + max(leftHeight, rightHeight);
}
}
return true;
}
};
int main() {
/*
1
/ \
2 2
/ \
3 3
/
4
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->right->right = new TreeNode(3);
root->left->left->left = new TreeNode(4);
Solution solution;
cout << (solution.isBalanced(root) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is pushed onto and processed from the stack only a constant number of times.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The heightMap may store the height of every node, while the explicit stack also requires additional traversal space.

FAQs

Q1. Is checking the height difference only at the root enough?

No. The root may satisfy the balance condition while a deeper node violates it. Every node in the tree must satisfy the condition.

Q2. Why is the Brute Force Approach slower?

It repeatedly recalculates heights of the same subtrees while checking different ancestors. These repeated traversals can lead to O(N²) time in a skewed tree.

Q3. Why does the Optimized DFS use -1?

All valid subtree heights are non-negative. Therefore, -1 can safely act as a special signal indicating that an unbalanced subtree has already been detected.

Q4. Why is post-order traversal suitable for this problem?

A node cannot determine whether it is balanced until the heights of both its children are known. Post-order processes the children first and the parent afterward.

Q5. What is the advantage of the iterative post-order approach?

It avoids recursive call-stack limits. Its trade-off is additional O(N) storage for explicitly storing computed subtree heights.

Binary Tree

Read Similar Blogs

Binary Tree

Parent and Distance - Introduction

Parent and Distance in a Binary Tree A binary tree normally stores connections from a node to its children: Left child Right child These connections make downward traversal straightforward. However...

117.9k
Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

Given the roots of two binary trees, root and subRoot , determine whether subRoot appears as a subtree of root . A subtree must match an enti...

67.9k
Binary Tree

Count Nodes in a Complete Binary Tree

Given the root of a complete binary tree , determine the total number of nodes present in the tree. In a complete binary tree: Every level except possibly the last is completely filled. Nodes in th...

54.2k
Comments0