Watch 10 video solutions for Balanced Binary Tree, a easy level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by take U forward has 419,271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |