STEP 13 · BINARY TREES · POST-ORDER AGGREGATION · EASY

Maximum Depth of Binary Tree

WHAT IT SAYS

Return the number of nodes on the longest path from the root down to a leaf.

WHAT IT'S REALLY ASKING

"The deepest path out of you must first step into one of your two children — there is nowhere else for it to go. So if each child could just tell you the deepest path out of THEM, your own answer is one comparison and a plus one. The whole problem is learning to believe the children."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Enumerate every root-to-leaf path

O(n) time — but conceptually per-path, and it obscures the structure

Walk from the root to every leaf, carrying a counter, and record the longest count you ever see. Explicitly generate the paths, or simulate them with a stack of (node, depth) pairs.

WHERE THE WORK IS WASTED — Paths through a tree share prefixes, and path-enumeration re-walks them. Every root-to-leaf path in the left subtree starts with the same first step, yet the path-centric framing treats each as its own journey from the root. The tree already merged those shared prefixes for you — that is what a tree IS — and thinking in paths un-merges them. The deeper cost is conceptual: you are managing global state (current depth, best so far) for a question the structure answers locally.

KEY OBSERVATION — THE UNLOCKlink

Your longest path is one step plus your best child's.

Take the deepest root-to-leaf path in the whole tree and look at its first move. It steps into the left child or the right child — there is no third option. And from that point on, it must be the deepest path within that child's subtree: if a deeper one existed down there, swapping it in would lengthen the total, contradicting that we picked the deepest. That is the optimal-substructure argument, and it converts the problem into a contract: depth(node) = 1 + max(depth(left), depth(right)). Each node needs exactly two numbers from below and does one comparison. The recursion bottoms out at the empty tree, whose depth is 0 — and note that the base case is the EMPTY tree, not the leaf. A leaf then computes 1 + max(0, 0) = 1 with no special-casing at all. Handle 'leaf' as a base case and you will write the same check twice and get null-children wrong once. The reason this file exists is not the recurrence — it is the discipline. When you write depth(left), you must treat it as a finished, trustworthy number, not something you mentally trace into. Every tree problem that follows (balance, diameter, path sums) is this same contract with a richer return value, and the people who struggle with those are the ones who never fully believed the recursion here.

Trust the children, add one

O(n) time, O(h) space for the recursion stack — O(log n) balanced, O(n) skewed

If the node is null, return 0. Otherwise return 1 plus the larger of the two recursive calls. Three lines. The BFS alternative — count how many levels a queue-based sweep peels off — computes the same number iteratively and is worth knowing for when the tree is deep enough to threaten the call stack.

WHAT YOU TRADED — Recursion's hidden cost is the stack: a skewed tree makes h equal to n, and a big enough input will overflow it — that is when the BFS level-count earns its keep. The transferable lesson is the contract itself: define precisely what your function returns for any subtree, trust that value from the children, and combine. Every hard tree problem is this pattern with a heavier payload.

WATCH THE IDEA RUN

CALL STACK — everyone here is still waiting on a child

stack empty — every branch explored

nodes that have reported 0

root's answer waiting

Nothing is known. Watch which direction the knowledge travels — it does not flow down from the root, it climbs up from the leaves.

step 1 / 12

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Trust the Subtree's Answer

YOU'LL SEE IT AGAIN WHEN

The quantity for a whole tree is a cheap function (max, sum, or, and) of the same quantity on the two subtrees.
You catch yourself mentally tracing into the recursive call instead of treating its return value as a finished fact.
Global path-thinking forces you to carry mutable state that a post-order return value would carry for free.

SAME BLUEPRINT, DIFFERENT PROBLEM

Balanced Binary TreeDiameter of Binary TreeMinimum Depth of Binary TreeCount Complete Tree Nodes

The bar isn't "solved it once." It's "could rebuild it from the observation."