Introduction to Root to Leaf Path Pattern

A root-to-leaf path problem accumulates state (a sum, a list of values, a boolean condition) while a DFS walks downward from the root, and finalizes/compares that state exactly when the recursion hits a node with no children — because only at a leaf is the "path" complete and meaningful to score against every other path.

Recognize the pattern

• Problem says "root to leaf", "any path from root ending at a leaf", or defines a path strictly as root→leaf (not node→node).
• You need something that depends on the whole path — sum, digit concatenation, all values, or "does any path satisfy X" — not just a single node's value.
• A leaf is explicitly node.left == null && node.right == null — nodes with only one child are NOT leaves and must keep recursing (a classic pitfall).
• Answer requires comparing/aggregating across multiple candidate paths (max, count, existence), which rules out a single top-down pass without carrying accumulated state.

Brute force vs optimal

Brute force: without any stored path or parent information, a bare root+leaf reference does not tell you which edges connect them. Recovering the path requires an O(n) DFS search from the root for every leaf (walking and backtracking until that leaf is matched), so recomputing all leaf sums this way costs O(n) leaves × O(n) search = O(n²) in the worst case. A slightly better brute force precomputes a parent-pointer map in one O(n) pass, then walks upward from each leaf to the root in O(h) — but that still pays O(n) upfront for the map, and walking "up from a leaf" only works if you can uniquely identify which node is the leaf in the first place (a bare value is not a unique identifier when duplicates exist). Either version does real extra work that the single-pass approach below needs zero of.

Optimal: one DFS pass that carries currentSum downward as a parameter (or return value). Each node is visited exactly once and does O(1) work, so the whole traversal is O(n) time — no path is ever reconstructed or re-walked.

Complexity, derived

Time: the recursion tree has exactly one call per tree node (n nodes), and each call does O(1) work (add value, check leaf, compare max) before making at most 2 recursive calls. Total work = n × O(1) = O(n) — strictly better than the O(n²) (or O(n) extra setup + O(n·h)) brute force above.

Space: no extra data structure holds all paths — only the call stack. Stack depth equals the current path length, bounded by the tree height h. So space is O(h): O(log n) for a balanced tree, O(n) worst case for a skewed (linked-list-shaped) tree.

Worked example

Tree: root=8, left=4 (leaf), right=9 with left child 1 and right child 6 (both leaves). Values: 8 → {4, 9 → {1, 6}}.

In the table below, each call receives currentSum as the sum accumulated before visiting the current node (the "incoming" value); the code immediately adds that node's own value to it before checking leaf status. The "sum after adding" column is what the code holds once that addition happens, and it's this post-add value that gets compared against maxSum at a leaf.

Three root-to-leaf paths exist: 8→4 (sum 12), 8→9→1 (sum 18), and 8→9→6 (sum 23). The last call to reach a leaf, findMaxSum(6, 17), produces the largest sum, so the traversal finishes with maxSum = 23 along the path 8→9→6.

Java

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

class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        findMaxSum(root, 0);
        return maxSum;
    }

    private void findMaxSum(TreeNode node, int currentSum) {
        if (node == null) return;
        currentSum += node.val;
        if (node.left == null && node.right == null) {
            maxSum = Math.max(maxSum, currentSum);
            return;
        }
        findMaxSum(node.left, currentSum);
        findMaxSum(node.right, currentSum);
    }
}

Go

import "math"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt64

    var findMaxSum func(node *TreeNode, currentSum int)
    findMaxSum = func(node *TreeNode, currentSum int) {
        if node == nil {
            return
        }
        currentSum += node.Val
        if node.Left == nil && node.Right == nil {
            if currentSum > maxSum {
                maxSum = currentSum
            }
            return
        }
        findMaxSum(node.Left, currentSum)
        findMaxSum(node.Right, currentSum)
    }

    findMaxSum(root, 0)
    return maxSum
}

Same shape as the Java version: currentSum is passed by value into the closure, so each recursive branch gets its own independent copy — sibling subtrees can never see each other's accumulated sum.

Pitfalls

• Treating a single-child node as a leaf — checking only node.left == null (or only right) will score an internal node as a completed path and silently produce a wrong (often smaller) max.
• Forgetting the null-node base case, causing a NullPointerException on the last level.
• Passing currentSum as a shared mutable field instead of by value/parameter — sibling branches then leak state into each other.
• Using this pattern for "any node to any node" path-sum problems (e.g., Binary Tree Maximum Path Sum on LeetCode) — that variant requires a different recurrence (return max downward gain, update a global at every node, not just leaves).
• When the answer is the list of values on each path (not a folded scalar), sharing one mutable list across the recursion without backtracking corrupts every stored path — push the node before recursing and pop it after both children return, or pass an immutable copy down. The by-value scalar version above sidesteps this precisely because it never shares mutable state.

When to use / when not

Use root-to-leaf DFS when the problem's definition of "path" is explicitly anchored at the root and terminates at a leaf (path sum, root-to-leaf number concatenation, path-exists-with-target-sum). Carry state downward as parameters — no extra memory beyond the stack.

Vs. BFS level-order: BFS can also enumerate root-to-leaf paths (tracking a partial path per queue entry) but costs O(n) extra space for the queue plus O(n) or more for stored partial paths, with no benefit unless you need shortest-path-by-level or level-synchronized processing — DFS is simpler and uses less space (O(h) vs O(n)) for pure path aggregation.

Vs. general tree DP (any-node-to-any-node paths): if the path doesn't have to start at the root, you need a bottom-up recurrence returning the best downward extension per subtree, not a top-down accumulator — don't reach for root-to-leaf DFS there.

Vs. "count any downward path summing to K" (Path Sum III, LeetCode 437): the path may start and end at any node as long as it goes strictly downward, so leaf-anchored accumulation is the wrong tool. The efficient answer carries a running prefix-sum from the root plus a hashmap of prefix-sum → count seen so far on the current root path; at each node the number of valid paths ending here is map[currentPrefix − K]. Crucially you must decrement that map entry as you unwind (the same backtracking discipline as the path-list case) so sums from one branch never leak into a sibling. This turns an O(n²) "try every start node" brute force into O(n).

Takeaways

• Accumulate path state as you descend; finalize/compare only at true leaves (both children null).
• One DFS pass, O(n) time, O(h) space — no need to re-walk paths, unlike the O(n²) (or O(n)-setup, identity-ambiguous) brute force of reconstructing each leaf's path after the fact.
• Passing state as a parameter (not a shared mutable field per branch) keeps sibling recursions independent — true in both the Java and Go implementations above.
• Distinguish this from any-node-to-any-node path problems, which need a different bottom-up recurrence.

Recall: Why is a node with only a right child not treated as a leaf in this pattern, and what bug results if you check leaf-ness by node.right == null alone?

Derived from classic root-to-leaf DFS treatments (e.g., LeetCode 112/113/129 path-sum family) and standard DFS complexity analysis for binary trees.