Log inSign up
easyleetcodeNot Started

Balanced Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1 · Example 1: Balanced Tree:

Input: root = [3, 9, 20, null, null, 15, 7]
Output: true
Explanation: Left subtree height is 1, right subtree height is 2. Difference is 1 <= 1.

Example 2 · Example 2: Unbalanced Tree:

Input: root = [1, 2, 2, 3, 3, null, null, 4, 4]
Output: false
Explanation: Subtree at node 2 has left height 2, right height 0. Difference is 2 > 1.

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -104 <= Node.val <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the bottom-up sentinel (-1) pattern for boolean tree validation.
  • Avoid O(n2) top-down repeated height calculations.
  • Handle short-circuit propagation in recursive calls.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Determine if binary tree is height-balanced.
  • Subtree height difference constraint <= 1.
  • Bottom-up validation with early pruning.

Algorithmic Decision Tree:

  • int check(node): if (!node) return 0;
  • lh = check(node.left); if (lh == -1) return -1;
  • rh = check(node.right); if (rh == -1) return -1;
  • if (abs(lh - rh) > 1) return -1;
  • return 1 + max(lh, rh);

Connected Patterns:

Maximum Depth of Binary TreeDiameter of Binary TreeValidate Binary Search Tree

1. Top-Down Height Comparison

Intuition

Compute height(left) and height(right). If difference > 1, return false. Otherwise return isBalanced(left) && isBalanced(right).

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return true.
  2. Step 2: lh = height(root.left), rh = height(root.right).
  3. Step 3: If abs(lh - rh) > 1 return false.
  4. Step 4: Return isBalanced(root.left) && isBalanced(root.right).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int height(TreeNode* node) {
10 if (!node) return 0;
11 return 1 + max(height(node->left), height(node->right));
12 }
13 bool isBalanced(TreeNode* root) {
14 if (!root) return true;
15 int lh = height(root->left);
16 int rh = height(root->right);
17 if (abs(lh - rh) > 1) return false;
18 return isBalanced(root->left) && isBalanced(root->right);
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n^2) — Repeated height computation takes O(n2) worst case on skewed trees.
  • Space complexity: O(h) — Call stack takes O(h) space.

2. Top-Down with Height Memoization

Intuition

Calculate and store all subtree heights in a map in postorder. Then verify balance top-down using O(1) height lookups.

When to apply: When caching subtree heights explicitly.

Algorithm

  1. Step 1: Compute and store height of each node in a map.
  2. Step 2: Check balance condition for each node using cached heights.
  3. Step 3: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 unordered_map<TreeNode*, int> heights;
10 int calcH(TreeNode* node) {
11 if (!node) return 0;
12 return heights[node] = 1 + max(calcH(node->left), calcH(node->right));
13 }
14 bool check(TreeNode* node) {
15 if (!node) return true;
16 int lh = node->left ? heights[node->left] : 0;
17 int rh = node->right ? heights[node->right] : 0;
18 if (abs(lh - rh) > 1) return false;
19 return check(node->left) && check(node->right);
20 }
21 bool isBalanced(TreeNode* root) {
22 calcH(root);
23 return check(root);
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n) — Precomputes heights in O(n) and validates in O(n).
  • Space complexity: O(n) — Map stores heights of all n nodes.

3. Bottom-Up DFS with Sentinel -1

Intuition

Define dfs(node). If node is null, return 0. Compute lh = dfs(node.left): if -1 return -1. Compute rh = dfs(node.right): if -1 return -1. If |lh - rh| > 1, return -1. Otherwise return 1 + max(lh, rh). The tree is balanced if dfs(root) != -1.

When to apply: Standard optimal solution in all interviews.

Algorithm

  1. Step 1: Define dfs(node):
  2. - If node == null return 0.
  3. - lh = dfs(node.left). If lh == -1 return -1.
  4. - rh = dfs(node.right). If rh == -1 return -1.
  5. - If abs(lh - rh) > 1 return -1.
  6. - Return 1 + max(lh, rh).
  7. Step 2: Return dfs(root) != -1.

Balance Check Trace for root = [3, 9, 20, null, null, 15, 7]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Node 9 is a leaf, returns height 1
Visual state
Values and pointers at this exact step
tree
Root
3
L
9 (h=1)
R
20 (h=2)

Node order shown; add connections to display explicit tree edges.

curr: 20
Check / comparison
Node 9 h=1, Node 20 h=2
Decision / next transition
Both subtrees balanced.
Why this step matters

Step 1: Node 9 is a leaf, returns height 1. Node 20 has leaves 15 and 7 (h=1), so node 20 has |1 - 1| = 0 <= 1 and returns height 2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int dfs(TreeNode* node) {
10 if (!node) return 0;
11 int lh = dfs(node->left);
12 if (lh == -1) return -1;
13 int rh = dfs(node->right);
14 if (rh == -1) return -1;
15 if (abs(lh - rh) > 1) return -1;
16 return 1 + max(lh, rh);
17 }
18 bool isBalanced(TreeNode* root) {
19 return dfs(root) != -1;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n) — Visits each node once in O(n) time, short-circuiting on first imbalance.
  • Space complexity: O(h) — Call stack depth is bounded by tree height O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down HeightO(n^2)O(h)Call height() recursively from top to bottom.Redundant subtree height computations.
2.Height MemoizationO(n)O(n)Store all heights in hashmap.Hashmap allocations.
3.Bottom-Up DFS with -1OptimalO(n)O(h)Return -1 immediately on imbalance, else return height.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns true (height 0).
  • Single node: root = [1] -> returns true.
  • Subtree unbalanced deep inside while root appears balanced.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why returning -1 as a sentinel flag is cleaner than passing boolean pointers or tuples.
  2. Emphasize that the bottom-up check runs in O(n) time, whereas the naive top-down is O(n2).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the bottom-up DFS approach return -1 instead of a boolean value?

Back to DSA Sheet