Maximum Depth of Binary Tree: The Top-Down DFS Pattern

Most people solve Maximum Depth of Binary Tree with one line: return 1 + Math.max(maxDepth(left), maxDepth(right)). That works, and it's clean. But it hides a decision that matters on every harder tree problem — which direction does information flow? That one-liner passes answers upward, from the leaves back to the root.

The top-down approach flips it. You carry the current depth downward as a parameter, and every time you touch a node you compare its depth against a running global maximum. Same O(n) cost, opposite data flow. Learning both is the difference between memorizing one tree solution and understanding the two traversal shapes — preorder (top-down) and postorder (bottom-up) — that every tree problem is built from.

The problem#

Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf. An empty tree has depth 0; a single node has depth 1.

The tree above has two leaves at depth 2 (node 9) and two at depth 3 (nodes 15 and 7). The longest root-to-leaf path passes through 3 → 20 → 15 (or 7), touching three nodes, so the answer is 3.

The bottom-up baseline#

The recursion nearly everyone writes first reasons from the bottom up. A node's depth is 1 plus the deeper of its two subtrees, and an empty subtree contributes 0.

Nothing is wrong with this — it's O(n) and idiomatic. But notice the mechanics: it makes no progress until it hits the leaves. Each call is stuck waiting for its two children to return numbers before it can compute its own. The answer bubbles up the call stack. That "wait for children, then combine" shape is postorder traversal, and it's the right tool when a node genuinely needs its subtrees' results (checking balance, summing paths). For plain depth, you never actually need a subtree's answer to know how deep the current node sits. That's the opening the top-down approach exploits.

The key insight: carry depth downward#

You already know a node's depth the moment you arrive there — you were told it by the parent. The root is at depth 1. Its children are at depth 2. Their children are at depth 3. So instead of computing depth on the way back up, pass it down as a second argument and increment it on each descent.

Then the maximum depth is simply the largest depth value you ever see. Keep one shared variable, update it at every node, and by the time the traversal finishes it holds the answer. Visiting the node before its children makes this a preorder traversal — process, then recurse.

This is the reframe: bottom-up returns values through the call stack; top-down threads state through a parameter and a shared accumulator.

The top-down solution#

Three things carry the whole approach:

• maxDepth starts at 0 and lives outside the recursion — it's the shared accumulator every call writes to.
• traverse(root, 1) kicks off at depth 1, because the root itself counts as one node on the path.
• depth + 1 on each recursive call. The first line of traverse records the current depth; then it descends left and right, each time one level deeper. curr.left && guards the call so we never recurse into a null child.

There's no return value from traverse at all. It's a pure side-effecting walk that leaves the answer in maxDepth.

Walkthrough#

Tracing root = [3, 9, 20, null, null, 15, 7]. The traversal is preorder, so we visit a node, update the max, then go left before right. maxDepth is the global accumulator carried across every call.

Two calls set new records — node 9 pushes the max to 2, node 15 pushes it to 3 — and node 7, sitting at the same depth, changes nothing. Because we recurse left before right, we reach 15 before 7, but the answer would be identical either way: the max only cares about the deepest node, not the order we find it.

Complexity#

Space is O(h), not O(n): the call stack only ever holds the frames along the current root-to-leaf path. For a balanced tree that's O(log n); for a fully skewed tree (a linked list of nodes) the height equals n, so the stack grows to O(n) in the worst case. This is identical to the bottom-up version — the two approaches have the exact same asymptotic cost. The difference is conceptual, not performance.

Common mistakes#

• Starting depth at 0 instead of 1. If the root passes traverse(root, 0), every depth is off by one and a single-node tree reports depth 0 instead of 1. The root counts as a node on the path, so it starts at 1.
• Declaring maxDepth inside traverse. It has to live in the outer scope. Put it inside the recursive function and each call gets its own copy, so updates never accumulate and the answer is lost on the way back up.
• Returning from traverse. The top-down version deliberately returns nothing — the answer lives in the shared variable. Trying to return a value confuses it with the bottom-up style and usually breaks one or the other.
• Recursing into null children. Without the curr.left && / curr.right && guards you'd call traverse(null, ...) and dereference null.left. Guard the descent, or add a if (!node) return; at the top of traverse.

Where this pattern shows up next#

Threading state downward through a parameter is the core preorder move, and it powers a whole family of tree problems:

• Path Sum — carry a running sum down instead of a depth, and check it at the leaves.
• Path Sum - Top Down — the same top-down accumulator pattern applied directly to root-to-leaf sums.
• Binary Tree Maximum Path Sum — the harder cousin, where a global max is updated during a bottom-up walk.
• Symmetric Tree — a top-down DFS that descends two subtrees in lockstep instead of one.

To watch the depth parameter travel down the tree and the global max tick up node by node, open the top-down Maximum Depth visualizer and step through it.

FAQ#

What is the difference between the top-down and bottom-up solutions to Maximum Depth of Binary Tree?#

They differ in how information flows. The bottom-up version returns each subtree's depth up the call stack and combines them with 1 + max(left, right) — a postorder walk that computes the answer on the way back up. The top-down version passes the current depth down as a parameter and updates a shared global maximum at every node — a preorder walk. Both are O(n) time and O(h) space; the difference is which direction the state travels, not efficiency.

Why does the traversal start at depth 1 instead of 0?#

Because depth here counts nodes, not edges. The root is one node on the longest path, so it sits at depth 1. Starting traverse(root, 1) makes a single-node tree correctly report depth 1 and a null tree report 0 (handled by the early if (!root) return 0). If you started at 0 you'd be counting edges, and every answer would come out one too small.

What is the time and space complexity of the top-down approach?#

Time is O(n), since each of the n nodes is visited exactly once and does constant work. Space is O(h), where h is the height of the tree, because the recursion stack only holds the frames along the current path from root to the deepest node in progress. For a balanced tree that's O(log n); for a completely skewed tree it degrades to O(n).

Why does maxDepth have to be declared outside the recursive function?#

Because it's a shared accumulator that every recursive call must read and write. If you declare it inside traverse, each invocation creates its own local copy, updates that copy, and discards it when the call returns — so the deepest values never make it back to the top-level caller. Keeping maxDepth in the enclosing scope lets a single variable collect the maximum across the entire traversal, which is the whole point of the top-down style.