Recursive DFS (post-order fold)

35 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Here is a small family tree of numbers. 3 is at the top. Below 3 sit 9 and 20. Below 20 sit 15 and 7. The question: how many levels deep is the tree? You can see the answer, 3, by looking. But a computer cannot "look"; it can only stand on one node and see that node's two children. So we need a way to get the answer by standing on nodes one at a time.

The by-hand method most people try is to trace every path from the top to every bottom node, writing down each path's length, then take the biggest. For our tree that is three paths: 3→9 (2 nodes), 3→20→15 (3 nodes), 3→20→7 (3 nodes). Fine for 5 nodes. But a tree with a million nodes can have half a million bottom nodes, and each path can be hundreds long. Writing every path means revisiting the top nodes hundreds of thousands of times.

Build the structure, one piece at a time

First, what is a tree? One node at the top (the root). Every node may have a left child and a right child, or none. A node with no children is a leaf. That is the whole structure. There is no clever extra memory; the trick is in how we ask the question.

Piece one: instead of asking "how deep is the whole tree", ask each node a smaller question: "how deep is the part below you?" A leaf answers 1 at once (just itself).

Piece two: a node that has children cannot answer alone, so it asks its left child, then its right child, waits for both numbers, and combines them: its depth is 1 + the larger of the two answers.

Watch it on the example. The root 3 asks 9. 9 is a leaf: answer 1. The root asks 20. 20 asks 15: a leaf, 1. 20 asks 7: a leaf, 1. 20 combines: 1 + max(1, 1) = 2. The root combines: 1 + max(1, 2) = 3. Done, and no path was written twice.

The order matters: children first, parent last. That is called post-order, and the function calling itself on each child is called recursion. The computer keeps a stack of unfinished questions: while 20 waits for 15, both 3 and 20 are "on hold".

Why it is correct

The rule we rely on: the answer for a node depends only on the answers of its two children, never on anything above it or beside it. For depth that is obviously true: the deepest path below 3 must go through 9 or through 20, so it is one step longer than the deeper of those two.

depth(v) = 1 + max(depth(left(v)), depth(right(v))), with depth(nothing) = 0

Leaves are the base case and are correct by definition. If every child's answer is correct, the formula makes the parent's answer correct. Working upward from the leaves, every node ends up correct, including the root. The same shape works for "are these two trees the same" (same value here, and same on the left, and same on the right), for mirror symmetry, for inverting a tree (invert both children, then swap them) and for counting nodes (1 + left count + right count).

Why it is fast

Each node is asked exactly once and answers exactly once, doing a constant amount of work (a comparison and an addition). So the total work is proportional to the number of nodes n: O(n). The by-hand path listing was far more, because top nodes were rewritten in every path.

The hidden cost is the stack of questions on hold. It is as long as the longest chain from the root down, the height h. For a balanced tree that is about log₂ n (20 for a million nodes); for a tree that is really a long chain it is n, which is why very deep trees can overflow the recursion stack.

How to recognise it in an interview

The cue is a question about a whole tree whose answer can be assembled from the two halves: height, balance, equality, symmetry, count, sum. Say out loud: "I will define what each node returns, handle the leaf case, and combine the children's returns at the parent." In Maximum Depth of Binary Tree the return is the depth. In Same Tree you walk two trees side by side and return whether this pair matches and both child pairs match. In Balanced Binary Tree return the height but also mark the answer false the moment two child heights differ by more than 1.

02The idea in one line

Solve the children, then combine at the parent.

Reach for it when: Height, balanced, same/symmetric tree, invert, count nodes.

Cost: O(n) time, O(h) stack.

03The walk-through, step by step

The video works one example: Maximum Depth of [3,9,20,null,null,15,7]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Ask the root: how deep is the tree below you?
2. The root cannot answer yet: it asks its left child first
3. 9 has no children: it returns 1
4. Now the right child, 20, is asked
5. 20 asks its left child 15: a leaf, returns 1
6. Then its right child 7: also a leaf, returns 1
7. 20 combines: 1 + max(1, 1) = 2
8. Root combines: 1 + max(1, 2) = 3
9. Every node is visited once and answers once: O(n), stack depth O(h)

04Asked at Google

11 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trees: Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.