Maximum Depth of Binary Tree: The Bottom-Up DFS Every Tree Problem Reuses

Maximum Depth of Binary Tree is the problem that teaches you to trust the recursion. Its optimal solution is two real lines of logic, but writing them requires a mental shift most people fight at first: instead of walking down the tree counting as you go, you let each node ask its children how deep they are and add one.

That reframe — a node's answer is built from its children's answers — is the exact shape of postorder DFS, and it powers half the tree problems you'll ever see: diameter, balance checks, path sums, subtree comparisons. Get it clean here and the harder ones stop looking hard.

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 root node has depth 1.

The level-order array [3, 9, 20, null, null, 15, 7] describes that tree: 3 is the root, its children are 9 and 20, node 9 has two null children, and 20 has children 15 and 7. The longest root-to-leaf path is 3 -> 20 -> 15 (or 3 -> 20 -> 7), three nodes deep, so the answer is 3.

The brute force baseline#

The instinct many people reach for first: walk to every leaf, record how long each root-to-leaf path was, then return the longest one.

This gives the right answer, but it's doing bookkeeping the problem never asked for. It allocates an array, threads a running depthSoFar counter down every branch, special-cases leaf detection, and then spreads the whole list into Math.max. The depth information flows down the tree, so nothing accumulates naturally — every leaf independently reports its own distance and you compare them at the end. It works, but it's fragile and noisy for a question with a two-line answer.

The key insight: let depth flow back up#

Flip the direction. Don't push a counter down toward the leaves — pull depths up from them.

The depth of any node is just one plus the deeper of its two subtrees:

A null child contributes 0, which is the base case that stops the recursion. Every non-null node adds 1 for itself and defers the rest to its children. Because each node returns a finished number to its parent, the parent never has to know anything about the tree below its own children — it just takes the max of two values and adds one.

This is bottom-up (postorder) DFS: solve both subtrees fully, then combine. No shared array, no downward counter, no leaf special-case.

The optimal solution#

Read it top to bottom. The null check is the base case — an empty subtree has depth 0. Then the two recursive calls resolve the left and right subtree depths completely before the final line runs. Only once both leftDepth and rightDepth are real numbers does the node compute its own answer: 1 + Math.max(...). That returned value becomes the caller's leftDepth or rightDepth, and the same combine step fires one level up. The recursion carries the state — you never declare a running maximum yourself.

Walkthrough: root = [3, 9, 20, null, null, 15, 7]#

The calls fire top-down, but the answers resolve bottom-up, in postorder. Here is the order in which each call finishes and what it returns:

Node 9 resolves first: both its children are null, so 1 + max(0, 0) = 1. The two leaves under 20, namely 15 and 7, each resolve to 1 the same way. Now 20 has both its children's answers in hand — 1 and 1 — so it returns 1 + max(1, 1) = 2. Finally the root 3 combines its left child 9 (depth 1) with its right child 20 (depth 2): 1 + max(1, 2) = 3. The larger subtree wins, and 3 is the answer.

Notice the root never touched 15 or 7 directly. It only ever saw the two numbers its immediate children handed up. That containment is what makes the recursion so short.

Complexity#

Both approaches must touch all n nodes — you can't know the deepest leaf without looking — so time is O(n) either way. The win is space. Bottom-up DFS keeps only the current root-to-node chain on the call stack, so it uses O(h) memory, where h is the height. For a balanced tree that's O(log n); for a fully skewed tree (a linked-list-shaped tree) it degrades to O(n), which is the one case where an iterative BFS level-count can be safer.

Common mistakes#

• Returning 1 for a null node. The base case must return 0. If null returns 1, a single root reports depth 2 and every count is inflated. A leaf's depth comes from 1 + max(0, 0), so its null children must contribute zero.
• Confusing depth with node count. Maximum depth is the longest path length, not the total number of nodes. A tree with 7 nodes can have depth 3 (balanced) or depth 7 (fully skewed).
• Adding before recursing incorrectly. Some rewrites try Math.max(maxDepth(left) + 1, maxDepth(right) + 1). That's equivalent here, but the cleaner 1 + Math.max(left, right) adds the current node's 1 exactly once and reads as the recurrence it implements.
• Ignoring the skewed-tree stack. On a pathological chain of 10⁵ nodes, the recursion depth equals the node count and can overflow the call stack. If that's a real constraint, switch to an explicit stack or BFS.

Where this pattern shows up next#

The "combine your children's answers, add your own contribution" shape is the backbone of bottom-up tree recursion. These build directly on it:

• Maximum Depth of Binary Tree - Top Down — the same problem solved the other direction, passing depth down and updating a running max, so you feel the contrast.
• Balanced Binary Tree — returns subtree height and checks the left/right height gap in the same postorder pass.
• Diameter of Binary Tree — reuses this exact depth computation, but records leftDepth + rightDepth at every node along the way.
• Path Sum — the root-to-leaf traversal skeleton, carrying a running total instead of a depth.

You can also step through the visualizer to watch depths bubble up the tree and the call stack unwind, one node at a time.

FAQ#

What is the maximum depth of a binary tree?#

The maximum depth is the number of nodes on the longest path from the root down to the farthest leaf. An empty tree has depth 0, and a tree with just a root has depth 1. It is sometimes called the height of the tree. For the tree [3, 9, 20, null, null, 15, 7], the longest path is 3 -> 20 -> 15, which is three nodes, so the maximum depth is 3.

Why does the base case return 0 and not 1?#

Because null represents the absence of a node, so it contributes nothing to a path. When a real leaf node runs 1 + max(maxDepth(null), maxDepth(null)), it computes 1 + max(0, 0) = 1 — the leaf itself counts as depth 1, and its two empty children add nothing. If null returned 1 instead, every leaf would report depth 2 and the entire tree's count would be inflated by one at each level.

What is the time and space complexity?#

Time is O(n), where n is the number of nodes, because the algorithm must visit every node once to know which leaf is deepest. Space is O(h), where h is the height of the tree, because the recursion call stack holds one frame per level of the current path. For a balanced tree that's O(log n); for a completely skewed tree it degrades to O(n).

Can you solve maximum depth without recursion?#

Yes. A breadth-first search using a queue counts levels iteratively: process the tree one full level at a time, incrementing a counter for each level until the queue empties. That counter is the maximum depth. BFS uses O(w) space, where w is the widest level, and it sidesteps the deep-recursion stack overflow risk on heavily skewed trees, though the recursive DFS is shorter and more common in interviews.

Is maximum depth the same as the height of a binary tree?#

They refer to the same value when counted in nodes. Some textbooks define height in terms of edges rather than nodes, which makes it exactly one less than this node-count depth. LeetCode's Maximum Depth problem counts nodes, so an empty tree is 0 and a single node is 1 — that is the convention this solution follows.