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: You are given the root of a binary tree and must determine whether it is height-balanced. A binary tree is balanced when the height difference between the left and right subtree of every node is at most one.
Approach 1: Recursive Height Calculation (O(n^2) time, O(h) space)
This straightforward solution computes the height of the left and right subtree for every node, then checks whether the difference exceeds one. Use a recursive height(node) function that returns 1 + max(leftHeight, rightHeight). During traversal, repeatedly call this function while verifying the balance condition. The drawback is repeated work: the height of the same subtree may be recomputed multiple times. In the worst case (a skewed tree), this leads to O(n^2) time while the recursion stack uses O(h) space where h is the tree height.
Approach 2: Optimized Recursive Approach (O(n) time, O(h) space)
This method combines balance checking and height calculation in a single DFS traversal. Instead of computing subtree heights separately, the recursive function returns the height of the subtree while also detecting imbalance early. If a subtree is already unbalanced, return a sentinel value such as -1. Each parent node checks whether either child returned -1 or whether the height difference exceeds one. If so, propagate -1 upward. Otherwise return the computed height. Because each node is visited exactly once, the algorithm runs in O(n) time with O(h) recursion stack space.
The solution relies on a depth-first traversal pattern commonly used in tree problems. Specifically, it performs a post-order DFS so the algorithm processes child subtrees before evaluating the parent node. This pattern appears frequently in depth-first search problems involving structural checks or subtree properties.
Balanced tree checks are a fundamental concept in binary tree algorithms because many data structures (AVL trees, Red-Black trees) rely on height balance to maintain efficient operations. Practicing this problem helps build intuition for computing subtree properties during traversal.
Recommended for interviews: The optimized recursive approach is the expected solution. It demonstrates that you can avoid redundant computations by combining height calculation with the balance check in a single DFS. Mentioning the naive O(n^2) approach first shows you understand the baseline, while implementing the O(n) solution proves you can optimize recursive tree algorithms.
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.
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.
Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.
We define a function height(root) to calculate the height of a binary tree, with the following logic:
root is null, return 0.l and r respectively. If either l or r is -1, or the absolute difference between l and r is greater than 1, then return -1. Otherwise, return max(l, r) + 1.Therefore, if the function height(root) returns -1, it means the binary tree root is not balanced. Otherwise, it is balanced.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| Bottom-Up Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Height Calculation | O(n^2) | O(h) | Simple baseline approach when learning recursion on trees |
| Optimized Recursive DFS (Post-order) | O(n) | O(h) | Preferred interview solution that avoids repeated height calculations |
Balanced Binary Tree - Leetcode 110 - Python • NeetCode • 375,910 views views
Watch 9 more video solutions →Practice Balanced Binary Tree with our built-in code editor and test cases.
Practice on FleetCode