Tree DFS

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

When to use

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

Complexity

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).

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

How it works

Tree DFS picks an order — pre, in, or post — and recurses. The order choice matters: in-order on a 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.

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 LCA, returning the wrong node when both targets are in the same subtree by short-circuiting too early.
Forgetting that '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: BST sorted traversal, validate BST, kth smallest.
Post-order: subtree properties (height, balance, sum, diameter).
Path-collecting DFS with backtracking: root-to-leaf paths, path sum II.

Template

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

Problems using this pattern

Easiest first · Blind 75 above NeetCode 150

Practice these problems

Solve mode — formulate the approach, then reveal. 5 problems.