Balanced Binary Tree
Problem
Given the root of a binary tree, return true if the tree is height-balanced, and false otherwise. A binary tree is height-balanced if for every node, the difference in height between its left and right subtrees is at most 1.
- The number of nodes in the tree is in the range [0, 5000]
- −10⁴ ≤ Node.val ≤ 10⁴
Example
root = [3,9,20,null,null,15,7]trueThe tree has root 3 with left child 9 and right subtree rooted at 20. The left subtree height is 1 (node 9), and the right subtree height is 2 (nodes 20, 15, 7). The difference is 1, which satisfies the balanced condition. The algorithm recursively checks each subtree, confirming balance at every node, and returns true.
Approach
Straightforward Solution
A naive approach would separately compute the height of left and right subtrees for every node and check the balance condition, leading to repeated height calculations and O(n²) time complexity.
Core Observation
A binary tree is balanced if and only if every subtree is balanced and the height difference between left and right subtrees at every node is at most 1. This property can be checked recursively by combining balance status and height information from child nodes.
Path to Optimal
The key insight is to combine the height calculation and balance check in a single post-order DFS traversal. By returning both balance status and height from each recursive call, the algorithm avoids redundant height computations, achieving O(n) time complexity.
Optimal Approach
PreviewUse a DFS helper function that returns a tuple: (is_balanced, height). For each node, recursively obtain the balance and height of left and right subtrees…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited exactly once in the DFS traversal, and all operations at each node take constant time.
Space
O(h)
The recursion stack depth is proportional to the height h of the tree, which is O(n) in the worst case of a skewed tree and O(log n) for balanced trees.
Pattern Spotlight
DFS (Post-Order Traversal with State Aggregation)
When checking a property that depends on subtree information (like height and balance), use a post-order DFS that returns multiple pieces of state to avoid redundant computations and achieve linear time.
Solution
| 1 | class Solution:
|
| 2 | def isBalanced(self, root: TreeNode) -> bool:
|
| 3 |
|
| 4 | def dfs(root):
|
| 5 | if not root:
|
| 6 | return [True, 0]
|
| 7 |
|
| 8 | left, right = dfs(root.left), dfs(root.right)
|
| 9 | balanced = (left[0] and right[0] and
|
| 10 | abs(left[1] - right[1]) <= 1)
|
| 11 |
|
| 12 | return [balanced, 1 + max(left[1], right[1])]
|
| 13 |
|
| 14 | return dfs(root)[0] |
Step-by-Step Solution
Define DFS Helper That Returns Balance and Height
| 4 | def dfs(root):
|
Objective
To define a DFS helper that returns both whether a subtree is balanced and what its height is.
Key Insight
The whole optimization comes from aggregating two pieces of state in one post-order traversal. The helper definition makes that contract explicit: each recursive call returns balance status and height together so the parent can decide its own state without recomputing subtree heights.
Interview Quick-Check
Core Logic
Use a helper that returns both balance status and height so the tree is processed in one pass.
State & Boundaries
The helper's return contract must stay consistent for every subtree, including the null base case.
Common Pitfalls & Bugs
If the helper returns only height, you lose the ability to prune balance logic cleanly without extra work.
Return Balanced Status and Height for Null Nodes
To define the base case for the recursion where an empty subtree is considered balanced with height zero.
Recursively Compute Left and Right Subtree Balance and Height
To gather balance status and height information from left and right subtrees for the current node.
Determine Current Node Balance and Height from Subtrees
To compute whether the current node is balanced and its height based on its children's results.
Return Final Balanced Status from Root Call
To initiate the DFS traversal from the root and return the overall balanced status of the tree.
4 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
balanced = (left[0] and right[0] andCheck if both subtrees are balanced and height difference is at most 1.
This condition directly encodes the definition of a balanced binary tree, ensuring the current node satisfies the balance property.
if not root:Check if the current node is null (base case).
This base case defines that an empty subtree is balanced and has height zero, which is essential for terminating recursion correctly.
return [True, 0]Return balanced status True and height 0 for null nodes.
Returning (True, 0) here ensures that leaf nodes can compute their balance and height based on these base values, enabling correct bottom-up aggregation.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why does combining the balance check and height calculation in a single DFS traversal improve efficiency compared to separate computations?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Balanced Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Balanced Binary Tree drill