Recursion is the native language of trees — every subtree is itself a tree, so you solve for the children and combine at the current node. The only real decision is which traversal order to use: post-order when children must report back first, pre-order when the parent decides first, in-order for BST sorted properties, and BFS when level membership matters.
A tree DFS function returns the finished answer for the subtree rooted at a node. So you never trace the call stack — you assume the recursive calls on the children already worked, and your only job is to combine their two answers and handle the current node. Solve it for one node and the whole tree solves itself.
The single biggest unlock in trees: stop imagining the entire stack of calls. When you write dfs(node), pretend you are standing on one node and you have a magic assistant. You call dfs(node.left) and it hands you back the correct, finished answer for the entire left subtree. Same for the right. You do not care how it got that answer — you trust it.
Now your whole job shrinks to three moves: take the left answer, take the right answer, and combine them with what this node contributes. That is the entire problem. The recursion handles all the depth for free.
( 1 ) ◄ YOU are here. You only do 3 things:
/ \ 1. ask left child for its answer
/ \ 2. ask right child for its answer
( 2 ) ( 3 ) 3. combine + handle THIS node
/ \
( 4 ) ( 5 ) The recursive call on ( 2 ) ALREADY returns the
correct answer for the whole left subtree.
Don't trace into it. Assume it works.Strip away the specific problem and every tree DFS is the same three moves. Read it as a sentence, not as code: null is the empty subtree (return the identity); recurse left and right and trust them; fold the two answers together with this node.
dfs(node): # RETURNS the answer for the subtree at `node`
if node is null: # 1. BASE CASE — the empty subtree.
return identity # 0 for heights/sums, true for checks,
# null for node-builders, [] for lists.
left = dfs(node.left) # 2. TRUST IT — this is the correct answer
right = dfs(node.right) # for the entire left / right subtree.
# (pre-order work would go ABOVE the two calls;
# post-order work goes HERE, after both returned.)
return combine(left, right, node.val) # 3. fold children + this nodeThe only things that change between problems are: what the function returns, what the null base case returns, and how you combine. For height it's 1 + max(left, right); for “count nodes” it's 1 + left + right; for “is balanced” it's a height-or-sentinel. Same skeleton, different filling.
Here is one small tree visited three ways. Notice the walk is identical— depth-first, left before right. The only thing that moves is the moment you record (“visit”) the node itself:
Tree: ( A )
/ \
( B ) ( C )
/ \
( D ) ( E )
PRE-ORDER (self, left, right) : A B D E C ◄ touch node BEFORE children
IN-ORDER (left, self, right) : D B E A C ◄ touch node BETWEEN children
POST-ORDER (left, right, self) : D E B C A ◄ touch node AFTER children
Same walk, same shape. The ONLY difference is the moment you "visit self".When the question mentions levels, depth, right-side view, zigzag, or minimum depth, DFS is awkward — switch to BFS, which sweeps the tree one horizontal ring at a time. Picture concentric rows expanding from the root:
( A ) ── level 0 (queue: [A])
/ \
( B ) ( C ) ── level 1 (queue: [B, C])
/ \ \
( D ) ( E ) ( F ) ── level 2 (queue: [D, E, F])
BFS drains the queue level by level. Snapshot levelSize = queue.length
at the top of each ring, loop exactly that many times, enqueue children
for the NEXT ring. The for-loop boundary IS the level boundary.The whole trick is the level-size snapshot. A queue mixes levels together, so before you start a ring you record how many nodes are in it (levelSize = queue.length) and loop exactly that many times. Children you enqueue during the loop belong to the next ring:
bfs(root): # process the tree level by level
if root is null: return
queue = [root]
while queue is not empty:
levelSize = length(queue) # SNAPSHOT this ring before it grows
for i in range(levelSize): # loop EXACTLY one level's worth
node = queue.pop_front()
do something with node # this whole loop = one level
if node.left: queue.push(node.left) # enqueue next ring
if node.right: queue.push(node.right)Faced with an unfamiliar tree problem, don't start typing the recursion. Climb these rungs in order — the code falls out at the bottom:
0 for heights/sums, true for “all nodes satisfy…”, null for builders, -∞ for max-gain.left and right (which you trustare correct), write the one expression that produces this node's answer. This is usually a max, min, +, &&, or a comparison with node.val.The highest-leverage habit in trees: before coding, say the return contract out loud as one sentence, then sanity-check it on the two smallest inputs — a leaf and null. If those two agree with your combine step, the recursion is almost certainly correct (induction does the rest).
dfs(node)returns the height of the subtree.” Null → 0; leaf → 1 + max(0, 0) = 1. ✓check(node, low, high) returns whether the subtree is a valid BST entirely inside (low, high).” Null → true. ✓dfs(node) returns the best path sum that starts at node and goes down one side.” Null → 0; the answer-through-a-node lives in a global.left + right + node.valto the parent. That value bends back down into both children, so the parent can't extend it — it must return only max(left, right) + node.val (one side) and stash the both-sides total in the global. If your return sentence has the word “through,” that's your tell to split it into a global.A whole class of tree bugs comes from checking a property using only a node and its immediate neighbors, when the property is actually about the whole path from the root. The fix is always the same: pass the accumulated constraint down as a pre-order argument.
left.val < node.val < right.val. A node deep in the right subtree can violate a far ancestor and still pass.(low, high) down: left tightens high = node.val, right tightens low = node.val. Every node is checked against its whole ancestry.Every tree problem has the same skeleton: base case on null, recurse on left and right children, then combine at the current node. Because every subtree is itself a tree with the same structure, you never need to think globally — just answer the question for the two children and decide what to return upward.
The mental model: "What does my left child tell me? What does my right child tell me? What do I compute from those two answers and my own value?" That question answered cleanly gives you the recursion.
Three DFS orderings; each unlocks a different class of problems:
When the problem asks about levels, depth layers, right-side view, zigzag, or minimum depth, reach for BFS with an explicit queue. The trick is snapshotting the queue length at the start of each level so you know when one level ends and the next begins.
levelSize = queue.length, then loop exactly that many times. Children enqueued during the loop belong to the next level and are not counted in the current one.A Binary Search Tree satisfies a strict ordering at every node: all nodes in the left subtree are less than the current node, and all nodes in the right subtree are greater. This unlocks two things:
h = O(log n); on a degenerate (sorted-input) tree h = O(n).node.left.val < node.val is not sufficient. A right-subtree node can be smaller than an ancestor. You must thread valid (low, high) bounds down every recursive call.left → self → right. Watch only where"self" falls relative to the two child calls.Reach for a tree traversal whenever the problem gives you a binary tree (or BST) node and asks for a property of the whole tree, a path, a level, or the structure itself. The traversal order is the decision — not whether to recurse.
| "depth / height / diameter / balanced" | post-order DFS — children report height first, parent computes from both |
| "level by level / right side view / level widths / zigzag" | BFS with a queue and a level-size snapshot loop |
| "is it a BST / kth smallest / in-range / sorted sequence" | in-order traversal (iterative or recursive) for BST sorted property |
| "serialize / clone / compare two trees / copy structure" | pre-order DFS — root visited first so structure is recorded top-down |
| "lowest common ancestor (LCA)" | BST: walk down using ordering; general tree: post-order checking left/right returns |
| "path sum / max path / gain along a path" | post-order DFS returning best downward contribution, update a global for path-through |
| "build tree from preorder + inorder (or inorder + postorder)" | divide & conquer: root from preorder, split inorder with an index map, recurse on halves |
visited set.n-node tree hits O(n) stack depth. For very large inputs, prefer iterative traversal with an explicit stack or queue to avoid stack overflow.When → Children's results must be known before the current node can be computed: height, diameter, max path sum, balanced check. Returns a value per subtree and updates a global for cross-subtree aggregates.
// Shared definition (LeetCode provides this)
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val; this.left = left; this.right = right;
}
}
// Pattern: post-order DFS returning a value per subtree, updating a global.
// Used for: height, diameter, max-path-sum, balanced check, etc.
let best = -Infinity; // or 0, or false — problem-specific global
function dfs(node: TreeNode | null): number {
if (!node) return 0; // base case — null contributes 0 (or -Infinity, etc.)
const left = dfs(node.left); // 1. recurse left
const right = dfs(node.right); // 2. recurse right
// 3. combine at this node (post-order: children computed first)
best = Math.max(best, left + right + node.val); // e.g. max path through node
// 4. return the "best contribution upward" — only ONE branch goes up
return Math.max(left, right) + node.val;
}-1as a sentinel for "unbalanced" so you propagate failure without a separate boolean.When → The problem cares about which level a node is on: level-order output, right-side view, minimum depth, level averages, zigzag traversal.
// Shared definition (LeetCode provides this)
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val; this.left = left; this.right = right;
}
}
function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const result: number[][] = [];
const queue: TreeNode[] = [root];
while (queue.length) {
const levelSize = queue.length; // snapshot: how many nodes are in THIS level
const level: number[] = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift()!;
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}level array, or in DFS pass depth and record only the first node visited at each new depth when traversing right-first.When → You need the BST's nodes in sorted order, or you want to stop early (kth smallest). The iterative form lets you pause mid-traversal without recursion.
// Shared definition (LeetCode provides this)
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val; this.left = left; this.right = right;
}
}
// Iterative in-order: visits BST nodes in ascending order.
// Use for: kth-smallest, validate BST values, flattening to sorted array.
function inOrder(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let cur: TreeNode | null = root;
while (cur || stack.length) {
// Descend as far left as possible
while (cur) { stack.push(cur); cur = cur.left; }
cur = stack.pop()!; // visit (left subtree exhausted)
result.push(cur.val);
cur = cur.right; // move to right subtree
}
return result;
}When → Confirming a tree satisfies the BST invariant. Thread the valid range down every call; never compare only to the immediate parent.
// Shared definition (LeetCode provides this)
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val; this.left = left; this.right = right;
}
}
// Correct approach: carry valid (low, high) bounds down the tree.
// Every node must satisfy low < node.val < high.
function isValidBST(root: TreeNode | null): boolean {
function check(
node: TreeNode | null,
low: number,
high: number,
): boolean {
if (!node) return true;
if (node.val <= low || node.val >= high) return false;
return check(node.left, low, node.val) &&
check(node.right, node.val, high);
}
return check(root, -Infinity, Infinity);
}node.val; going right tightens the lower bound to node.val.Every recursive tree function must handle node === null before accessing node.left or node.right. Leaf nodes have null children — if you skip the null check the function crashes on the very first leaf it reaches. Return the appropriate identity value: 0 for heights/sums, true for structural checks, null for node-returning functions.
Checking node.left.val < node.val at every node is wrong — a node deep in the right subtree of an ancestor could be smaller than that ancestor and still pass local checks. Always carry explicit (low, high) bounds from the root down and reject any node whose value falls outside the inherited range.
In max-path-sum, a global variable should be updated with left + right + node.val (the full path through the current node), but the function must return only max(left, right) + node.val. Returning the full path value causes the parent to add it again, counting nodes twice and producing wrong answers.
In-order (left → root → right) on a BST gives sorted ascending output. Pre-order and post-order do not. A frequent interview slip is applying pre-order logic where in-order is needed (kth smallest, sorted merge) or using in-order on a general binary tree expecting sorted output.
left + right + node.val for a path through the current node. Return only max(left, right) + node.val upward.#102Binary Tree Level Order TraversalBFS with level-size snapshot: collect exactly levelSize nodes per iteration into a sub-array.#297Serialize and Deserialize Binary TreePre-order with null markers: serialize writes root before children, deserialize rebuilds in the same order using an index pointer or queue of tokens.#572Subtree of Another TreeDFS over every node of the main tree; at each node call a sameTree helper. O(m·n) overall but clean and accepted.#105Construct Binary Tree from Preorder and Inorder TraversalDivide & conquer: preorder[0] is the root, find it in inorder to split left/right sizes, recurse on each half. Build an inorder index map for O(1) splits.#98Validate Binary Search TreeDFS carrying (low, high) bounds; going left updates high = node.val, going right updates low = node.val. Never compare only to the immediate parent.#230Kth Smallest Element in a BSTIn-order traversal (iterative is cleaner for early exit); decrement a counter at each visit and return when counter reaches 0.#235Lowest Common Ancestor of a Binary Search TreeWalk down using BST ordering: if both p and q are less than node go left; if both greater go right; otherwise current node is the LCA.#543Diameter of Binary TreePost-order height function; at each node update a global best with left_height + right_height (the diameter through that node). Return max(left, right) + 1 upward.#110Balanced Binary TreePost-order returning height or -1 as a sentinel for unbalanced. If either child returns -1, or |left - right| > 1, propagate -1 upward immediately.#199Binary Tree Right Side ViewBFS: take the last node of each level. Alternatively DFS right-first, recording only the first node encountered at each new depth.#1448Count Good Nodes in Binary TreePre-order DFS carrying the maximum value seen on the path from root. A node is good if node.val >= pathMax; count it and update pathMax for children.#236Lowest Common Ancestor of a Binary TreeFind the deepest node that has both p and q as descendants with a single post-order recursion: a node whose left and right subtrees each return a target is the LCA; otherwise bubble up whichever side found one. No BST property needed.#173Binary Search Tree IteratorStream a BST in sorted order with next()/hasNext() by simulating in-order traversal on an explicit stack: seed the leftmost spine, and after each pop push the left spine of the right child. Amortized O(1) per call, O(h) space.#337House Robber IIIMaximize loot on a binary tree where adjacent (parent–child) houses cannot both be robbed: a post-order DFS returns a [rob, skip] pair per node, the tree analog of the linear House Robber state machine. O(n).