Binary Trees: Recursion and the Right Traversal

Two binary-tree problems can look almost identical and still need completely different code — because of what each recursive call has to carry. Maximum Depth sends a number up from its children. Validating a BST pushes a range down into them. Maximum Path Sum does both and stashes a third answer outside the recursion entirely. Up, down, or outside: that direction of flow is the axis this hub is built on, and it decides everything from which traversal you write to what your function signature looks like.

A binary tree is a recursive definition made concrete — a node holding a value and two smaller trees — so you don’t so much apply recursion to a tree as read it off the structure.

Lean on the recursion

Maximum depth is the whole idea in miniature:

int maxDepth(TreeNode node) {
    if (node == null) return 0;                       // base case: empty tree
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

You didn’t write a loop or manage a stack — the call stack is the traversal. Ask each child for its depth, take the bigger, add one. It’s the same “solve the subproblems, then combine” move as dynamic programming, only here the subproblems are subtrees and the recursion hands you the order for free. What shifts from one tree problem to the next is not that combine step — it’s what each call carries through it.

The traversal follows from what you carry

Which order you visit in isn’t arbitrary — the natural choice follows from when a node can compute its answer, even though several problems admit more than one valid order:

• Post-order (children, then node) is the workhorse. Use it whenever a node’s answer depends on its children’s answers: depth, diameter, whether a subtree is balanced, maximum path sum. You recurse first and act on the way back up.
• Pre-order (node, then children) flows information down. Process the node, then hand something to the children — a running path sum, a max-so-far for counting “good” nodes, the root you write first when serializing.
• In-order (left, node, right) is the BST specialist: on a binary search tree it visits values in sorted order, which is the entire trick behind validating a BST or finding its kth-smallest element.
• BFS (a queue, level by level) is the odd one out — no recursion, just a queue — and it’s what you reach for the moment a problem says “by level”: level-order output, or a right-side view that wants the last node of each row.

Naming the traversal first turns most of these problems into fill-in-the-blank.

What the recursion carries

Maximum Path Sum is where all three directions collide at once, which is why it trips so many people. Each call returns the best single downward path so a parent can extend it — but the best complete path, which may bend through a node using both children, is kept in a global maximum, because a bent path can’t be passed up without breaking the recurrence. Confuse “what I return” with “what I’m answering” and the whole thing collapses; keeping the returned value and the tracked answer separate is the trick.

On a BST, order is the whole advantage

A binary search tree adds one promise — everything left of a node is smaller, everything right is larger — and that promise is just binary search living in a data structure. Searching, inserting, or finding the lowest common ancestor all become “compare, then go left or right,” an $O(h)$ walk down one path. Two cautions the problems love: validating a BST needs a range passed down (a node can be larger than its parent yet still violate an ancestor’s bound), not a parent comparison; and the in-order-is-sorted fact is what makes kth-smallest a simple counted walk rather than a heap.

Reading the fifteen

Sorted by what the recursion produces, NeetCode’s tree set stops looking like fifteen puzzles:

• Returns a number — Maximum Depth, Diameter, Count Good Nodes.
• Returns a boolean — Same Tree, Subtree of Another Tree, Balanced, Validate BST.
• Rebuilds or emits structure — Invert, Construct from Preorder & Inorder (the preorder’s first value is the root; find it in the inorder to split the two subtrees, then recurse), Serialize and Deserialize (pre-order with explicit nulls).
• Needs a traversal choice or global state — Level Order and Right Side View (BFS), Kth Smallest and LCA of a BST (in-order / the BST walk), Maximum Path Sum (post-order plus a global).

The shape shows up everywhere

This post-order “a node’s answer is its value plus what its children report” is not an interview toy. It’s exactly how du computes a directory’s size — a folder’s total is its own files plus the totals its subfolders hand back — and how a filesystem, the DOM, or a database’s B-tree index all get walked. The day the recursion clicked for tree depth, the recursive directory-size script I’d copied a dozen times finally stopped being magic. Trees are one of the few patterns you’ll use far more outside the interview than in it.

References

• NeetCode 150 — Trees — the fifteen problems behind this hub.