core idea
A tree problem is a traversal wearing a costume. The recursion always looks the same — visit left, visit right, do something with the current node — and the only thing that changes between problems is when “do something” happens relative to the two recursive calls. Get that placement right and half the tree section of an interview is just this template with a different line inside it.
| traversal | visit order | when you want it |
|---|---|---|
| preorder | node, then left, then right | do work before descending — copy, serialize, print top-down |
| inorder | left, then node, then right | walk a BST in sorted order |
| postorder | left, then right, then node | combine children’s answers into the parent’s — height, sum, diameter |
when to reach for it
- The problem hands you a
TreeNodeexplicitly — this is recursion-first territory, not the queue-and-grid world of BFS/DFS. - You need every value in sorted order and you’re told (or can assume) the tree is a BST → inorder.
- A node’s answer depends on what its children compute first — height, sum, “is this balanced” → postorder, children report up, parent combines.
- You’re transforming, copying, or printing the tree root-first, doing work at a node before touching its subtrees → preorder.
- The problem explicitly asks for an iterative solution, or you’re worried about recursion
depth on a skewed tree → the same traversal, with an explicit
Stack<TreeNode>standing in for the call stack.
universal template
One function, three traversals — only the position of the “visit” line moves:
public void Preorder(TreeNode? node, List<int> output)
{
if (node is null) return; // base case: nothing here, stop recursing
output.Add(node.Val); // VISIT HERE -> preorder (node, left, right)
Preorder(node.Left, output);
Preorder(node.Right, output);
}
public void Inorder(TreeNode? node, List<int> output)
{
if (node is null) return;
Inorder(node.Left, output);
output.Add(node.Val); // VISIT HERE -> inorder (left, node, right)
Inorder(node.Right, output);
}
public void Postorder(TreeNode? node, List<int> output)
{
if (node is null) return;
Postorder(node.Left, output);
Postorder(node.Right, output);
output.Add(node.Val); // VISIT HERE -> postorder (left, right, node)
}
// standard interview definition
public class TreeNode(int val = 0, TreeNode? left = null, TreeNode? right = null)
{
public int Val = val;
public TreeNode? Left = left;
public TreeNode? Right = right;
}Every problem below is one of these three shapes, sometimes returning a value instead of appending to a list, sometimes carrying extra state (a running best, a pair of bounds) down or up alongside the recursion. The shape of the function never changes.
the one question to ask
Does this node’s answer need something its children computed first? If yes, you want postorder — recurse into both children, then combine. That single question is behind maximum depth, diameter, balanced-tree checks, and most of the “hard” tree problems you’ll meet later. If the answer is no and you’re just walking top-down, preorder is simpler.
problems
Swap children everywhere — your first "traversal in a costume".
Postorder in disguise: children answer first, parent combines.
Postorder + a global best — the shape behind a dozen hard tree problems.
Inorder (the important one), preorder, and postorder as reversed preorder.
Inorder must be strictly increasing — or pass down (min, max) bounds.
Walk from the root: the split point is the answer. (LC 236 for general trees.)
cheat sheet — trees
recognize it
- Problem hands you a
TreeNode(not a graph/grid) and talks about parent/child structure directly - "Every node's answer depends on its children" (height, sum, balanced-check) -> postorder
- "Give me the values in sorted order" on a tree the problem calls or implies is a BST -> inorder
- "Do this without recursion" / recursion-depth or stack-overflow worry -> same traversal with an explicit
Stack<TreeNode> - Two node references + a BST -> walk from the root, let ordering pick the direction, no need to search both sides
key tricks
- One recursive skeleton, three traversals: only the position of the
output.Add(node.Val)line changes (before, between, after the two recursive calls) - Postorder = "children answer first, parent combines" — whenever a node's return value needs
leftANDrightalready computed, you're doing postorder even if you didn't plan it - Diameter-style problems: check-and-update a running best at EVERY node (
left + right), but stillreturna smaller number (1 + max(left, right)) up to the parent — two different questions, one walk - BST bounds-threading: pass
(lower, upper)DOWN through the recursion instead of comparing only to the immediate parent —node.Val <= lower || node.Val >= uppercatches violations from any ancestor, not just the direct one - Postorder iteratively = preorder with push order flipped (
leftbeforeright), producingnode,right,left, then.Reverse()
common bugs
- Off-by-one between edges and nodes:
MaxDepthcounts NODES (single node = depth 1), diameter counts EDGES (left + right, no+1) — mixing the two conventions up is the #1 tree bug - Comparing a node only to its immediate parent instead of threading full bounds down — passes locally, fails globally, and only shows up on trees where a deceptive node sits several levels from the ancestor it actually violates
- Seeding BST bounds with
int.MinValue/int.MaxValueinstead oflong— breaks the moment a real node value equals the sentinel - Forgetting the
+ 1(height) or including it where it doesn't belong (diameter'sleft + rightneeds no+1,Height's return does) - Swapping two fields with plain sequential assignment (
a.Left = a.Right; a.Right = a.Left;) instead of a tuple/temp swap — the second line reads back what the first line just overwrote