Given a binary tree, determine if it is height-balanced.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
Constraints:
[0, 5000].-104 <= Node.val <= 104Problem Overview: Given the root of a binary tree, determine whether the tree is height-balanced. A binary tree is balanced if the height difference between the left and right subtree of every node is at most one.
Approach 1: Recursive Height Calculation (O(n²) time, O(h) space)
This method checks the balance condition at every node by computing the height of its left and right subtrees separately. For each node, you recursively calculate height(node.left) and height(node.right), then verify that the absolute difference is at most 1. After that, you recursively validate that both subtrees are balanced. The drawback is repeated height calculations: each height computation traverses part of the tree again, leading to O(n) work per node in the worst case. For skewed trees this degrades to O(n²) time, while recursion stack usage remains O(h) where h is tree height.
This approach is straightforward and mirrors the definition of a balanced tree. It's useful for understanding the problem and for small inputs where repeated traversal cost is negligible. The solution relies on standard recursion patterns used in tree problems.
Approach 2: Optimized Recursive DFS (O(n) time, O(h) space)
The optimized approach combines balance checking with height computation in a single depth-first traversal. Instead of recalculating heights, the recursive function returns the height of the subtree while also detecting imbalance. If either subtree is already unbalanced, the function propagates a sentinel value such as -1. During recursion, you compute the left height, then the right height, and immediately check abs(left - right) > 1. When this condition occurs, return -1 to signal imbalance.
This eliminates redundant work because each node's height is computed exactly once. The algorithm visits every node a single time, giving O(n) time complexity with O(h) recursion stack space. The technique is a classic postorder traversal used in many depth-first search problems on binary trees.
Recommended for interviews: The optimized DFS approach is the expected solution. Interviewers want to see that you avoid repeated height computations and combine multiple checks in a single traversal. Starting with the naive recursive idea shows understanding of the definition, but recognizing and implementing the O(n) postorder DFS demonstrates stronger algorithmic thinking.
This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.
In this C implementation, a recursive function height is used to determine the height of each node's left and right subtree. For each node, we verify if the difference in height is more than 1. The solution exploits recursion to calculate tree height in a bottom-up manner.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack.
This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.
We use a helper struct Result holding both height and balanced state. The checkBalance function recurses over nodes, aggregating this data, and halting early if imbalance is detected.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.
| Approach | Complexity |
|---|---|
| Recursive Height Calculation | Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack. |
| Optimized Recursive Approach | Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Height Calculation | O(n²) | O(h) | Good for understanding the definition of a balanced tree or when implementing a quick baseline solution. |
| Optimized Recursive DFS | O(n) | O(h) | Preferred solution for interviews and production code because it computes height and balance in one traversal. |
L15. Check for Balanced Binary Tree | C++ | Java • take U forward • 419,271 views views
Watch 9 more video solutions →Practice Balanced Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor