The single most useful skill in the recursion track is not writing recursive functions. It is being able to say, at any point, what is on the stack and what each frame is waiting for. Everything else follows from that.
A frame is three things
- →Its arguments — the values this particular call received.
- →Its local state — anything computed so far inside this call.
- →Its return address — which line it will resume on when the call below it finishes.
When you trace by hand, write those three things per frame, one frame per line, newest at the bottom. That is the entire method.
Worked example
On a tree with root 3, left child 9, right child 20, the stack after the first descent reads: depth(3) waiting at line 4, then depth(9) waiting at line 4, then depth(None) about to return 0 at line 2. The 0 returns into depth(9), which binds l = 0 and moves to line 5.
Write which line each frame is parked on. Almost every tracing mistake is really a mistake about where a frame resumes.
Three places people go wrong
First: assuming both recursive calls happen together. They do not. depth(node.left) runs completely — its entire subtree — before depth(node.right) begins. If you are imagining a breadth-first spread, you are imagining the wrong algorithm.
Second: forgetting that locals are per frame. Every live call has its own l and r. People trace as though there is one shared l, which produces answers that look plausible and are wrong.
Third: treating the base case as an afterthought. The base case is the only thing that ever returns a concrete value. Every other frame returns a function of values that came from below it. Write the base case first, and trace it first.
Most tree problems have the same shape
Once you can read the stack, you notice that a large fraction of tree problems are post-order with a return value: recurse left, recurse right, combine, return. What differs between problems is only the combine step.
Maximum depth: BASE is 0, COMBINE is 1 + max. Diameter: BASE is 0, COMBINE returns the height while updating a global best with left + right. Balanced check: return the height, or a sentinel meaning unbalanced. Same skeleton, different combine.
When to stop tracing and convert
If the depth can reach 10^5 — a linked list, a degenerate tree, a path graph — hand-tracing will not save you, because the recursion itself will not survive. Convert to an explicit stack. It is five extra lines and removes an entire class of failure that raising the recursion limit only postpones.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.