Introduction to Tree Depth First Search Pattern

Introduction to Tree Depth-First Search Pattern

Tree DFS solves problems by recursing into a node's children first and only combining their answers once both return — turning "what is true about this whole subtree" into "what is true about the current node, given what my children reported," which mirrors the tree's own recursive definition (a tree is a value plus two smaller trees).

Recognize the pattern

• The problem talks about root-to-leaf paths, path sums, path existence, or "diameter/height/longest path."
• The answer at a node depends on an aggregate (min, max, sum, count) of its subtrees, not on siblings or ancestors directly.
• You need to go all the way down to a leaf before you can decide anything about a path.
• State naturally decomposes as f(node) = combine(f(node.left), f(node.right), node.val).

Brute force → optimal

Brute force: enumerate every root-to-leaf path explicitly (e.g., collect each path into a list as you DFS, sum it at the leaf, then scan all sums for the minimum). This does the same tree walk but pays extra memory to materialize every path — O(n) paths of average length O(log n) to O(n), so O(n log n) to O(n²) extra space/time just for storage.

Optimal: never materialize the paths. Fold the sum into the return value on the way back up — each node returns "the minimum leaf-path sum achievable from me downward," so the parent combines two numbers instead of two lists of paths.

Complexity from first principles

Each of the n nodes is visited exactly once, doing O(1) work (one comparison, one addition) per visit ⇒ O(n) time. There is no other traversal or repeated work, so this is tight — not a bound loosely covering something smaller.

Space: the recursion stack holds one frame per node on the current root-to-node path, so the stack depth equals the tree height h. That gives O(h) auxiliary space: O(log n) for a balanced tree, O(n) for a degenerate (linked-list-shaped) tree.

Worked example

Tree: root = [-1, 2, 3, 4, 5, 1] → -1 has children 2 and 3; 2 has children 4 and 5; 3 has right child 1.

Final answer: 3, matching path -1 → 3 → 1.

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int minPathSum(TreeNode root) {
        if (root == null) return Integer.MAX_VALUE; // no path here
        if (root.left == null && root.right == null) return root.val; // leaf

        int leftSum = minPathSum(root.left);
        int rightSum = minPathSum(root.right);

        // if one child is missing, only the existing side is a valid path
        if (root.left == null) return root.val + rightSum;
        if (root.right == null) return root.val + leftSum;

        return root.val + Math.min(leftSum, rightSum);
    }
}

Pitfalls

• Forgetting the one-child case: naively doing min(minPathSum(left), minPathSum(right)) when one child is null silently uses Integer.MAX_VALUE as a "path," which is usually harmless here but breaks the equivalent max-sum or path-count variants — always check for a missing child explicitly.
• Treating a node with one child as a leaf: a leaf must have both children null; a single-child node is not a valid path endpoint.
• Stack overflow on skewed trees: O(h) space becomes O(n) on a degenerate tree, which can blow the call stack for n in the tens of thousands — convert to an iterative DFS with an explicit stack if input size is unbounded.

When to use / when NOT — trade-offs

Use Tree DFS (post-order, bottom-up accumulation) whenever the answer at a node is a function of its subtrees' answers: height, diameter, path sums, subtree validation (e.g., BST check), lowest common ancestor. Avoid it when the problem is inherently level-based (shortest path in an unweighted tree/graph, level-order output, "nodes at distance k") — BFS is the named alternative there, since it explores level by level in O(n) time with O(w) space (w = max width), and guarantees minimum-depth answers first, which DFS cannot do without extra bookkeeping. DFS also loses to BFS when you need to short-circuit as soon as you hit the shallowest match.

Pre-order vs post-order — pick by data flow. If a node's answer needs information from above it (the running root-to-node sum, the current depth), carry that state down as a parameter on the way in — that is a pre-order (top-down) use. If a node's answer needs information from below it (subtree height, subtree sum, "is this a valid BST"), compute the children first and combine on the way back up — that is post-order (bottom-up). Height, diameter, and the classic binary-tree LCA are post-order; "path sum from the root" is top-down carry. LCA sketch (LeetCode 236): recurse; if the node is p or q, return it; if both the left and right recursive calls return non-null, this node is the LCA (p and q live in different subtrees); otherwise bubble up whichever side is non-null.

Vs. Morris traversal (O(1) auxiliary space): if even the O(h) recursion stack is unaffordable, Morris traversal threads temporary links from each node to its in-order predecessor and achieves O(1) extra space with O(n) time — but it temporarily mutates the tree, is far harder to write correctly, and is only worth it when memory is the hard constraint; the recursive O(h) DFS is the right default everywhere else.

Takeaways

• Post-order DFS lets each node return a summary of its subtree so the parent only combines two numbers, not two path lists.
• Time is O(n) because each node does O(1) work once; space is O(h), bounded by tree height, not node count.
• Always special-case a missing child — treating a null-returning child as a valid path is the most common bug in this pattern.

Recall: Why is the space complexity of recursive Tree DFS O(h) rather than O(n), and when do these coincide?

Compiled from standard tree-DFS treatments (recursion-based subtree aggregation) and CS interview-prep pattern catalogs on tree path problems.