DSA problem
Balanced Binary Tree
Given the root of a binary tree, determine if it is height-balanced. A binary tree is height-balanced if, for every node in the tree, the heights of its two child subtrees differ by no more than 1. An empty tree is height-balanced by definition.
A naive solution computes the height of every subtree by recursion, then re-walks the tree comparing left and right heights at each node. That approach is correct but costs O(n²) time in the worst case (a skewed tree), because the height function is invoked on every node and each call can itself walk a path of length O(n).
The optimal post-order approach computes height and balance simultaneously in a single pass. As the recursion unwinds, each call returns the height of the subtree rooted at that node — unless the subtree is unbalanced, in which case it returns a sentinel value of -1 to short-circuit the entire traversal. A node propagates -1 upward immediately if either child reported -1 or if the heights of its two children differ by more than 1.
Because every node is visited exactly once and performs constant work, the algorithm runs in O(n) time and uses O(h) call-stack space. The sentinel pattern is a classic post-order technique: collapse multiple pieces of information (height + validity) into a single return value so the recursion does not need extra parameters or shared state.
Examples
root = [3,9,20,null,null,15,7]trueroot = [1,2,2,3,3,null,null,4,4]falseroot = []trueConstraints
- The number of nodes in the tree is in the range [0, 5000].
- -10^4 <= Node.val <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.