Tree DFS Pattern

CodingJunior2 min read · 13 problemsUpdated Oct 28, 2026

Recursive or stack-based depth-first traversal; pre/in/post order.

When to Use It

Path sums, tree property checks (balanced, BST), serialization, lowest common ancestor.

Classic example: Path sum: does any root-to-leaf path equal target?

How It Works

Tree depth-first search (DFS) picks an order: pre, in, or post, and recurses. The order choice matters: in-order on a binary search tree (BST) yields sorted values; post-order is needed when a node's computation depends on its children (subtree sums, heights, balance checks); pre-order is for serialization or building structure top-down.

The recursion's return value is the design decision. For 'maximum path sum' you return the best single-arm extension to the parent but track the best two-arm answer in a closure or instance variable, mixing the two is the most common bug. For 'is balanced', returning height (with -1 as a sentinel for imbalance) folds two passes into one.

Iterative DFS uses an explicit stack and is needed when recursion depth would blow the JVM/Python stack (skewed trees with millions of nodes). Morris traversal goes further to O(1) extra space by temporarily threading nodes, but it's rarely worth the complexity in an interview unless explicitly asked.

Key Insight

The post-order pattern of 'recurse first, then compute using children's returns' lets a single O(n) traversal answer questions like height, balance, and subtree sums without re-walking, the recursion itself is the dynamic-programming table.

BFS visits by level (1-2-3-4-5-6). DFS dives down one branch first (1-2-4-5-3-6).

Templates

void dfs(TreeNode node /*, accumulator */) {
    if (node == null) return;
    // pre-order work here
    dfs(node.left);
    dfs(node.right);
    // post-order work here
}

def dfs(node):  # plus any accumulator
    if not node:
        return
    # pre-order work here
    dfs(node.left)
    dfs(node.right)
    # post-order work here

Common Pitfalls

Mixing the value returned to the parent with the global answer being tracked, e.g. returning the two-arm path sum upward when only single-arm extensions are valid.
For lowest common ancestor (LCA), returning the wrong node when both targets are in the same subtree by short-circuiting too early.
Forgetting that 'binary search tree (BST) validation' requires passing down min/max bounds, not just comparing to immediate parent.
Mutating shared state (a list) without backtracking when collecting paths.
Recursing without a null base case, NPE'ing on leaf children.

Variations

Pre-order: capture/serialize top-down.
In-order: binary search tree (BST) sorted traversal, validate BST, kth smallest.
Post-order: subtree properties (height, balance, sum, diameter).
Path-collecting depth-first search (DFS) with backtracking: root-to-leaf paths, path sum II.

Big O

Time: O(n)
Space: O(h)

Each node is visited once. The recursion stack depth is the tree height h: O(log n) for balanced trees, O(n) in the worst case (skewed tree).

Next PatternTwo Heaps