Call stack one frame per dfs call · newest on the right · badge = returned height, ✗ = returned false
public boolean isBalanced(TreeNode root) { return dfs(root).balanced;}private Res dfs(TreeNode root) { if (root == null) { return new Res(true, 0); } Res left = dfs(root.left); Res right = dfs(root.right); boolean balanced = left.balanced && right.balanced && Math.abs(left.height - right.height) <= 1; return new Res(balanced, 1 + Math.max(left.height, right.height));}private static class Res { boolean balanced; int height; Res(boolean balanced, int height) { this.balanced = balanced; this.height = height; }}
- root
- —
- left
- —
- right
- —
- balanced
- —
- return
- —
Why it works
- Brute force checks each node with a fresh height call on both children. Heights are recomputed at every ancestor: O(n²) on a chain, O(n log n) on a bushy tree.
- Return two facts at once. A subtree is balanced only if both children are balanced and their heights differ by at most 1. So each call hands its parent a
Res(balanced, height), and the parent never has to look below its children. - Post-order, one visit per node. Badges fill in from the leaves to the root, each in O(1) from its two children: O(n) time, O(h) stack.
- Pitfall: checking only the root. A tree whose root sides have equal height can still hide a lopsided node lower down; the
left.balanced && right.balancedpart carries that failure up. - Speed-up: return −1 as the height of an unbalanced subtree and stop early. Same pattern as Diameter of Binary Tree (543).