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
Use 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. The current node is balanced if both subtrees are balanced and their heights differ by at most 1. The height is 1 plus the maximum of the two subtree heights. The final answer is the balance status returned from the root.
Time
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] |
| 1 | class Solution { |
| 2 | public boolean isBalanced(TreeNode root) { |
| 3 | return dfs(root)[0] == 1; |
| 4 | } |
| 5 | |
| 6 | private int[] dfs(TreeNode root) { |
| 7 | if (root == null) { |
| 8 | return new int[] {1, 0}; |
| 9 | } |
| 10 | |
| 11 | int[] left = dfs(root.left); |
| 12 | int[] right = dfs(root.right); |
| 13 | boolean balanced = left[0] == 1 && right[0] == 1 && |
| 14 | Math.abs(left[1] - right[1]) <= 1; |
| 15 | |
| 16 | return new int[] {balanced ? 1 : 0, 1 + Math.max(left[1], right[1])}; |
| 17 | } |
| 18 | } |
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
| 5 | if not root:
|
| 6 | return [True, 0]
|
Objective
To define the base case for the recursion where an empty subtree is considered balanced with height zero.
Key Insight
An empty subtree is trivially balanced and has height zero. This base case anchors the recursion and allows leaf nodes to compute their balance and height correctly by building up from null children.
Interview Quick-Check
Core Logic
Returning (True, 0) for null nodes establishes the base condition that empty subtrees are balanced with height zero.
State & Boundaries
This base case prevents null pointer errors and terminates recursion properly.
Recursively Compute Left and Right Subtree Balance and Height
| 8 | left, right = dfs(root.left), dfs(root.right)
|
Objective
To gather balance status and height information from left and right subtrees for the current node.
Key Insight
By recursively calling the helper on left and right children, the algorithm aggregates necessary information to determine the current node's balance and height. This post-order traversal ensures children are processed before their parent, enabling bottom-up computation.
Interview Quick-Check
Core Logic
The recursive calls return tuples containing balance and height, which are essential to compute the current node's state.
State & Boundaries
The recursion naturally terminates at leaf nodes due to the base case for null children.
Determine Current Node Balance and Height from Subtrees
| 9 | balanced = (left[0] and right[0] and
|
| 10 | abs(left[1] - right[1]) <= 1)
|
| 12 | return [balanced, 1 + max(left[1], right[1])]
|
Objective
To compute whether the current node is balanced and its height based on its children's results.
Key Insight
The current node is balanced if both subtrees are balanced and their heights differ by at most one. The height is one plus the maximum height of the two subtrees. This logic encapsulates the definition of a balanced binary tree and height calculation in a single step.
Interview Quick-Check
Core Logic
Balance is the conjunction of left and right subtree balance and the height difference condition; height is 1 plus the max of subtree heights.
Common Pitfalls & Bugs
Forgetting to check both subtree balance statuses or incorrectly computing height leads to wrong results.
Return Final Balanced Status from Root Call
| 14 | return dfs(root)[0] |
Objective
To initiate the DFS traversal from the root and return the overall balanced status of the tree.
Key Insight
The root's balance status reflects the entire tree's balance. By returning the first element of the tuple from the DFS call, the algorithm provides the final answer succinctly.
Interview Quick-Check
Core Logic
Returning dfs(root)[0] extracts the balanced status from the tuple returned by the helper.
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.
return [balanced, 1 + max(left[1], right[1])]Return the current node's balanced status and height.
Returning both values allows the parent node to use this information for its own balance and height calculation, enabling the recursive aggregation of state.
left, right = dfs(root.left), dfs(root.right)Recursively compute balance and height for left and right subtrees.
This post-order traversal step gathers necessary subtree information before evaluating the current node, enabling efficient combined balance and height computation.
return dfs(root)[0]Return the balanced status of the entire tree from the root.
Extracting the balanced status from the tuple returned by dfs(root) provides the final answer to the problem.
def dfs(root):Define the DFS helper that computes subtree balance and height together.
Defining a helper that returns both balance status and height establishes the post-order contract used by the entire solution.
abs(left[1] - right[1]) <= 1)Calculate the absolute difference between left and right subtree heights.
Computing the height difference is critical to verify the balance condition; this value must be at most 1 for the node to be balanced.
Test Your Understanding
Why does combining the balance check and height calculation in a single DFS traversal improve efficiency compared to separate computations?
Because it avoids repeated height calculations for the same subtrees, reducing the time complexity from O(n²) to O(n) by computing height and balance status simultaneously during a single post-order traversal.
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