patternDSA/Tree DFS

Core Pattern → Pattern 16

Tree Depth First Search

Recurse down, collect on the way back up. The call stack IS your backtracking — no explicit undo needed. Two types: root-to-leaf paths and any-node paths.

Frequency:★★★★★

·~30 min·Intermediate·7 problems

Prev Tree Breadth First Search

The Core Shock

Iterative path tracking requires explicit undo. Messy. Recursive DFS backtracks for free. Natural.

Iterative + explicit stack

O(n) · messy

Must manually copy path at each push, then undo on pop

Recursive DFS

O(n) · clean

Call stack IS the backtracking. path.pop() = one line undo.

The insight: recursion gives you a free undo. When you append to a path list before the recursive call and pop after it, the path automatically reflects exactly the nodes on the current root-to-node path — no manual bookkeeping needed.

Two Tree DFS Types

Know which type before writing a single line.

Root-to-Leaf Paths

Path starts at root and must reach a leaf. Carry info (sum, path list, number) downward. Check condition at the leaf (both children null).

if not node.left and not node.right:
    return accumulated == target

Binary Tree Path SumAll Paths for a SumSum of Path NumbersPath With Given Sequence

Any-Node Paths (Going Down)

Path can start and end anywhere (but only goes downward). Use prefix sum HashMap: for each node, count paths ending here by checking (current_sum - target) in the map.

count = prefix_map.get(curr - target, 0)
prefix_map[curr] = prefix_map.get(curr,0)+1
# ... recurse ...
prefix_map[curr] -= 1  # backtrack

Count Paths for a SumPath Sum IIIMax Path SumTree Diameter

The 3-Step Framework

The 3-step DFS skeleton — works for both types with one change.

Base case: null node + leaf check

Two base cases every time. (1) Null node: return False/0/None immediately. (2) Leaf node (no children): check your condition and return. The leaf check IS the answer for root-to-leaf problems.

if not node: return False          # null
if not node.left and not node.right:
    return node.val == remaining   # leaf check

For 'return upward' problems (diameter, height): null returns 0, no leaf check needed. Just compute left + right and return max.

Recurse: carry state downward or collect upward

Root-to-leaf: pass updated state (remaining-=node.val, path.append, number=number*10+val) into children. Any-path prefix: update the HashMap, recurse both children, then undo the HashMap update.

# Root-to-leaf: carry downward
path.append(node.val)
dfs(node.left,  remaining - node.val, path)
dfs(node.right, remaining - node.val, path)
path.pop()   # backtrack

# Return upward: collect from children
left_h  = dfs(node.left)
right_h = dfs(node.right)
return 1 + max(left_h, right_h)

The key difference: root-to-leaf PASSES state into children (downward). Return-upward problems RECEIVE state from children (upward) via return values.

For global max: use nonlocal, not return

Diameter and max path sum need BOTH children's contributions to update the answer, but can only RETURN one arm upward. Use a nonlocal variable for the global max updated inside the recursion.

max_diam = 0
def height(node):
    nonlocal max_diam
    lh = height(node.left)
    rh = height(node.right)
    max_diam = max(max_diam, lh + rh)  # use both
    return 1 + max(lh, rh)             # return one

The return value serves the PARENT. The nonlocal variable captures the ANSWER. These are different: the diameter-through-a-node can't be returned upward because the parent can only use one arm.

Pattern Recognition

DFS vs BFS — two seconds to decide.

Use Tree DFS When

"Path sum", "path exists", "root-to-leaf"

Collect all paths satisfying a condition

"Sum of path numbers" (path as a number)

Path can be any-node-to-any-node (downward)

"Diameter", "longest path between two nodes"

"Maximum path sum" through any nodes

Validate a path matches a given sequence

Depth/height of tree (naturally recursive)

Common Pitfalls

Leaf check: using 'not node.left or not node.right' (wrong)

All paths: forgetting path.pop() after recursion → stale path

All paths: appending path instead of list(path) → alias bug

Count paths: forgetting prefix_counts[sum] -= 1 (backtrack)

Diameter/max sum: returning both-arm value instead of one arm

Max path sum: forgetting max(0, gain) — negative arms should be dropped

Null base case: not returning 0 (for height/sum) when node is None

Count paths prefix: must initialize {0:1} for paths from root

On this page