I'm working on the maximum depth of a binary tree problem and wrote this TypeScript solution:
function maxDepth(root: TreeNode | null): number {
if (root == null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}
I understand the code from a high-level perspective, but I struggle with the design process—especially imagining a function calling itself. Initially, I tried to think of it as searching in one direction, counting to the end, and then starting over, but that approach didn't work. How should I reason about what the recursive calls are doing?
4 Answers
Try the ‘black box’ approach. Pretend you have a magic function that correctly returns the depth of any smaller tree. For the current node, call that function on root.left and root.right, take the larger result, and add one for the current node. Then handle the case where root is null. Once the logic works with the imaginary function, replace the magic function with maxDepth itself. That leap of faith is the key to designing many recursive solutions.
Most recursive problems can be organized around two questions: what is the simplest input that can be answered immediately, and how can the current input be reduced to a smaller version of the same problem? Here, an empty tree has depth 0. Every nonempty tree reduces to its left and right subtrees, and the current node combines those answers with 1 + Math.max(leftDepth, rightDepth). You can also write the same algorithm iteratively with an explicit stack or queue, but recursion is a natural fit because the data itself is nested.
A recursive call is not a one-way jump. Each call gets its own local variables and waits for its child calls to return. You can picture the call stack: a call is pushed when entering a node, calls are made for the children, and then the frame is removed when the result is returned. For a null node, the function immediately returns 0. For a real node, both child calls finish first, then that node calculates and returns its result.
Writing down the stack frames or stepping through a small tree with a debugger can make this much clearer. The same variable names exist separately in each call.
Don’t start by imagining the entire traversal. Instead, assume the function already knows how to calculate the depth of either child subtree. Then ask: given the depths of my left and right subtrees, what is the depth of this node? The answer is 1 plus the larger value. The null check is the base case, and the calculation using the children is the recursive case. The traversal happens automatically as a consequence of those calls.
That’s a useful way to separate the logic from the control flow. You only need to prove that the base case is correct and that the combination step is correct when the child results are already known.
It is still technically a tree traversal, but you don’t have to manually plan every movement. Each call handles its own smaller subtree and returns a result to its caller.
The important part is not to trace every recursive call in your head. Trust the recursive assumption and focus on whether one node combines already-correct child results properly.