Patterns / Tree Traversal: DFS & BFS

Tree Traversal: DFS & BFS

DFS (recursion) bubbles information up from children; BFS processes the tree level by level.

What it is

Most tree questions are a traversal plus a small amount of bookkeeping. Depth-first search — usually plain recursion — naturally computes answers that depend on a node's subtrees (height, path sums, validity) by combining the results from its children. Breadth-first search uses a queue to visit the tree one level at a time, which is what you want for level-order output or the minimum number of steps in an unweighted setting.

When to use it — the signals

• "Depth", "height", "path sum", or anything defined recursively over subtrees.
• "Level order", "right side view", or per-level aggregation → BFS.
• "Minimum steps / shortest path" in an unweighted structure → BFS.

How it works

A representative implementation in Java:

// Maximum depth via DFS recursion.
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return 1 + Math.max(left, right);
}

Complexity

O(n) over the nodes. Space is O(h) for the recursion/queue, where h is the height (O(n) worst case).

Common pitfalls

• Missing the null base case, causing a NullPointerException.
• Using DFS where level structure matters (or BFS where subtree results matter).
• Deep recursion overflowing the stack on skewed trees — consider an explicit stack.

Practice problems

Classic problems where this pattern is the intended approach: Maximum Depth of Binary Tree, Binary Tree Level Order Traversal, Validate Binary Search Tree, Path Sum. Work through them on the Leet Study home page.