I'd solved around 80 tree problems by the time my second on site interview wrapped up. Most were mediums. Preorder, inorder, postorder, level order felt like second nature. Tree height and BST validation, written from scratch, half a dozen times each. But the medium I'd just bombed had a stateful postorder shape I didn't see in the moment, and 20 of the 35 minutes went to patching the wrong recursion.
On the train home I traced the solution by hand. It clicked in 90 seconds. The problem wasn't tree knowledge. What was missing was the skill of predicting how a recursive function would flow through the call stack, frame by frame, before writing any code.
What changed for me
- Mental simulation of the call stack is a separate skill from knowing traversal types.
- The six tree patterns split cleanly along one axis: which direction information flows.
- Stateful postorder problems look right at every node and wrong overall when you confuse the return value with the answer.
- BST validation looks structurally fine and is logically broken when you check only direct children.
- Practicing tree problems without simulating the call stack is what kept me stuck for months.
Where the recursion kept breaking
The approach had been treating tree problems the same way you'd treat array problems. Read the statement, sketch one small example, write code, test against the example, debug. On arrays that loop works fine because the traversal is linear and the bugs show up immediately. On trees the loop fails silently. The recursion executes, the values look plausible at every node, the test case passes on a small input, and a deeper tree from the interview question produces the wrong answer.
The symptom looked like a knowledge problem, so for a while the response was reading. Reread the postorder explanation. Try more medium problems. Next interview, freeze on something with the same shape. The reading wasn't the gap. The simulation skill was.
The fix turned out to be simpler than expected. Before writing any code for a tree problem, ask one question: which direction does information have to flow to get the answer? Down through parameters? Up through return values? Sideways with a queue?
That single question puts you into the right pattern category before you've written a line of code. It also forces you to predict what's going to happen on the call stack before running anything.
What I started doing differently
The protocol ran something like this. It was deliberately slower than the old read-and-code habit, and it was the part that closed the gap.
- Read the problem. Sketch a small concrete tree on paper. Not the example from the problem statement, a tree you make up.
- Ask the direction question. Does the answer for a node depend on what's above it, what's below it, or what's beside it?
- Pick a pattern. Down means preorder. Up means postorder. Sideways means level order. Stateful versions of each split off by whether a global accumulator is involved.
- Write one sentence describing what
f(node) returns. If you can't write the sentence, you've misidentified the pattern.
- Walk through the call stack on the sketched tree. Predict the order of recursive calls. Predict what each call returns. Note where global state changes if any.
- Only then start coding.
The whole protocol took 5 minutes the first few times. It saved 20 in debugging. After running it on 30 problems, the first five steps collapsed into about 60 seconds of thinking before any code got written.
What that looked like on diameter
The first problem I ran this protocol on was tree diameter. The diameter of a binary tree is the longest path between any two nodes, measured in edges.
Sketch a small tree. Root with a left subtree of depth 2 and a right subtree of depth 3.
Direction question: does the diameter at the root depend on what's above it (impossible, it's the root), what's below it (yes, the depths of the subtrees), or sideways (no)?
Information flows up. Postorder.
Sentence describing what f(node) returns: the height of the subtree rooted at node. The diameter accumulates globally.
That last detail is where stateful postorder lives. The return value is the local thing the parent needs (subtree height). The actual answer is a global thing updated at each node (the maximum of left_height + right_height seen anywhere in the tree).
def diameter(root):
longest = 0
def height(node):
nonlocal longest
if not node:
return 0
left = height(node.left)
right = height(node.right)
longest = max(longest, left + right)
return 1 + max(left, right)
height(root)
return longest
Walking the call stack:
height(left_child) runs first. Recurses down to the leaves, returns heights from the bottom up. At each node, updates longest with left + right.height(right_child) runs next. Same behavior on the right subtree.height(root) runs last. Gets left subtree's height (2) and right subtree's height (3). Updates longest with 2 + 3 = 5. Returns 1 + max(2, 3) = 4 (which is the tree's total height, not the answer).
The diameter is longest = 5. The return value of the top call is 4 (the height) and it isn't the answer. That separation between return value and answer is the entire pattern.
Earlier attempts at diameter kept trying to make the return value carry the answer directly. It doesn't work, because the diameter at a node combines information from two siblings, not from a single root-to-leaf path. The global accumulator is what handles that combination.
Why this works
The mechanism isn't deep, once you see it. Tree recursion is two recursive calls per node. The call stack pushes the parent frame, pushes the left child's call chain, pops back to the parent, pushes the right child's call chain, pops back to the parent. Two branches per frame.
What makes tree problems feel hard is that you have to predict this branching in your head before writing code. Once you can predict it, the choice between preorder, postorder, and level order falls out of the prediction itself. Down means the answer accumulates on the way down. Up means it accumulates on the way back. Sideways means the call stack is the wrong tool entirely and you should use a queue.
The maximum path sum lesson on Codeintuition was the one where this pattern finally became obvious to me, because it's stateful postorder with a meaner set of edge cases (negative values, single node paths, paths that pass through the root rather than ending at it). Watching the call stack trace through that problem frame by frame was what made the structure click for everything after it.
What I'd tell someone in the same spot
If you've solved 50+ tree problems and still freeze on unfamiliar ones, the gap is almost always the simulation skill, not the knowledge. More problems won't close it.
The shortest practice that helped me: take a tree problem you've solved before. Cover the solution. Sketch a small tree. Predict the order of recursive calls and what each call returns. Open the solution in a debugger and step through. Note where your prediction diverged from what actually happened.
Three rounds of that and the call stack stops feeling abstract. Five rounds and you can read a new tree problem, decide direction in 30 seconds, and start coding from a correct mental model.
Worth doing on every pattern category at least once. Stateless preorder. Stateless postorder. Stateful postorder. Root to leaf path. The BST inorder pattern. Level order with a queue. Once each of those patterns has a call stack trace burned into your head, the rest of the variants are small adaptations.
There's a longer version on my own blog that walks through the four BST-only patterns and the heap variants in more depth.
What's a tree problem that finally made the call stack visible to you in your head, where reading the textbook explanation hadn't? For me it was diameter. The protocol I built around it is what made every subsequent stateful postorder problem feel mechanical.