Binary Tree Patterns You Actually Need in Interviews
DFS/level‑order, recursion vs iteration, common traps
You can treat binary tree questions as a handful of reusable patterns, not a grab‑bag of one‑off tricks.
Big picture: three patterns
In most interviews, tree problems resolve into three ideas.
Depth‑first traversals (in‑order / pre‑order / post‑order) for “touch every node” logic, especially on BSTs.
Level‑order (BFS) for anything involving “by level,” “shortest path,” or “first/last node on a level.”
Path/subtree recursion for questions about “sum/max/min on some path/subtree” (e.g., max path sum, diameter, balanced tree).
If you can do these with both recursion and iteration and talk through complexity and edge cases, you’re better prepared than most candidates.
Pattern 1: in‑order and friends
For DFS traversals, memorize “what do I do at each node” and “when do I do it.”
In‑order (left, root, right): default for BST problems (sorted order, kth smallest, validate BST, median).
Pre‑order (root, left, right): good for serialization/deserialization and “copy this tree” style problems.
Post‑order (left, right, root): use when the answer at a node depends on its children (height, diameter, max path sum, distribute coins, delete tree).
Interview‑ready talking points.
Time: visit each node once → O(n).
Space (recursive): call‑stack O(h) where h is height; worst‑case O(n) on skewed trees.
Space (iterative): explicit stack also O(h); interviewer mainly cares that you can express either.
Example mental template (in‑order, recursive).
Recurse left.
“Do work” at current node (add to list, check order, update counter).
Recurse right.
You can drop almost any BST question into that template and just change the “do work” line.
Pattern 2: level‑order (BFS)
Level‑order = queue + “process current level before moving on.”
Use it when the prompt mentions:
“level,” “row,” “layer,” “width,” “zigzag,” “next pointers,” “left/right side view,” “shortest path.”
Distance in edges (minimum depth, nearest leaf, shortest transformation using a tree as a graph).
Standard queue template.
Push root.
While queue not empty, pop nodes of the current level (size = queue length at loop start), process them, and push their children.
Example: left side view.
For each level, remember the first node you see (or last, depending on traversal order) and append to result; everything else is boilerplate BFS.
Talking points.
Time O(n).
Space O(w), where w is max width (up to O(n)); that’s your answer if asked about worst case.
Recursion vs iteration in interviews
Most interviewers are fine with recursion as long as you can reason clearly about the call stack.
When recursion is preferred.
Tree problems with simple, top‑down or bottom‑up definitions (height, max path sum, validate BST).
When clarity matters more than worst‑case stack depth and the tree isn’t absurdly deep.
When iteration is worth showing.
The prompt explicitly says “no recursion” or “use iteration/stack/queue.”
You’ve just written a recursive solution; offer a quick “I can also do this iteratively with an explicit stack if you’d like,” especially for in‑order or pre‑order.
You want to highlight awareness of stack‑overflow risks or tail‑recursion limitations.
How to articulate the tradeoff.
Recursion: simpler and closer to the math definition, but uses call‑stack space O(h) and can overflow on very deep trees.
Iteration: a bit more code, but makes stack/queue usage explicit and sometimes easier to optimize.
Common traps (and how to avoid them)
These are the mistakes that actually cost offers, not off‑by‑one in your for‑loop.
Losing track of null and leaf cases: always handle empty tree, single node, and skewed tree; say this out loud before coding.
Mutating shared state incorrectly in recursion: be clear what each call returns vs what you track in outer scope (e.g., global max path sum, best answer so far).
Forgetting that recursion depth = height: mention stack space explicitly in your complexity analysis; interviewers listen for it.
Mixing up traversal orders: write a tiny example tree and trace your algorithm for in‑order/pre‑order/post‑order; don’t rely on memory under pressure.
Ignoring BST properties: for any BST question, ask yourself “can I do better than O(n) by using ordering?” before you brute‑force.
Over‑engineering: if the problem is “print nodes level by level,” you do not need fancy data structures; a queue is enough.
An easy practice loop is: pick a LeetCode/Tech Interview Handbook tree problem, solve it once with recursion, once with iteration (if reasonable), and then explain to an imaginary junior what your traversal order is doing at each node.