Given a binary tree, determine if it is height-balanced. A binary tree in which the left and right subtrees of every node differ in height by no more than 1.
root = [3,9,20,null,null,15,7]trueroot = [1,2,2,3,3,null,null,4,4]falseroot = [1,2,3,4,5]truenode == null → return 0 (null height is 0)L = height(node.left) — if L == −1, propagate −1 immediatelyR = height(node.right) — if R == −1, propagate −1 immediately|L − R| > 1 → this node is unbalanced, return −11 + max(L, R) — the actual height of this balanced subtreeUsing −1 as sentinel avoids a second pass. As soon as any subtree is unbalanced, all ancestor calls propagate −1 upward instantly — O(n) single-pass check. The recursion visits every node exactly once in post-order (children before parent), so when we check |L−R|, both subtree heights are already available. If the root receives a real height (≥ 0), the tree is balanced.
You could compute the height of both subtrees at every node, from scratch. That repeats the same height work again and again, which is O(n²) on a chain. Instead, compute heights bottom up, just once.
Write a height function that also checks the balance as it goes. It returns the real height when the subtree is balanced. It returns −1 as a signal when it finds any imbalance. Once a child returns −1, pass −1 straight up without more work. The tree is balanced if the root does not return −1.
Return the height, and use −1 as an error signal. Bottom up turns O(n²) into O(n).
Run the animation above on your own input, or watch the 2:07 video explanation of Balanced Binary Tree with a dry run and Java code.