Introduction to Leaf Processing Pattern

A leaf-processing problem is solved by running a full tree traversal (DFS or BFS) and applying a check-and-accumulate step only at the moment a node satisfies left == null && right == null. When the problem only cares about a leaf's own value or an order-independent aggregate (sum, count, max), the traversal order does not change the answer — only which extra state (path sum, depth, parent side) is easiest to carry down to that check. But when the problem is order-sensitive — for example "leftmost leaf value" or "leaves left to right" — the traversal choice is part of correctness: DFS (left before right) yields leaf order directly, while BFS gives level order, which is a different (and usually wrong) order for that class of question. So the rule is: pick any traversal for order-independent aggregates; pick DFS specifically when the required output order matches DFS's left-to-right leaf visitation.

Recognize the pattern

• Problem statement mentions "leaf", "leaf sum", "deepest leaves", "leftmost leaf value", or asks for a value/count that only leaves contribute to.
• You need something true at the leaf that depends on the path taken to reach it (sum so far, depth, whether it is a left child) — that data must be threaded as a traversal parameter, not recomputed.
• No pruning is possible in general: every leaf might matter, so you cannot stop early like in search problems.
• Check whether the required output has an order requirement (e.g. left-to-right) — if so, that constrains which traversal is valid, not just which is convenient.

Brute force vs optimal

Brute force: traverse the whole tree collecting every node into a list, then filter the list for leaves in a second pass. Correct but wastes O(N) extra memory and a second O(N) pass for no benefit.

Optimal: do the filtering inline during the single traversal — test node.left == null && node.right == null at each visit and accumulate directly (sum, count, or add to result list) before recursing further. One pass, no throwaway storage.

Complexity, derived

Time: the traversal (DFS or BFS) visits each of the N nodes exactly once, and the leaf test plus accumulation at each node is O(1) work. Total work = N × O(1) = O(N). No amount of cleverness beats this — you cannot know a node is a leaf without visiting it.

Space: DFS uses the call stack, whose depth equals the path length from root to the current node — bounded by tree height H, so O(H) (O(log N) balanced, O(N) skewed). BFS instead holds an explicit queue that at its widest holds one full level, so its space is O(W) where W is the max level width (up to O(N/2) in a complete tree). Result storage (the leaf list itself) is O(L) where L ≤ N is the leaf count, common to both.

Worked example

Tree: 1 is root, left child 2, right child 3; 2's children are 4 and 5; 3 is childless.

DFS visits left-subtree leaves before backtracking to the right subtree, giving left-to-right leaf order for free — this is why DFS (not BFS) is the correct choice, not just a convenient one, when order matters.

Java implementation

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;

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

class LeafProcessor {
    // DFS: preserves left-to-right leaf order, O(N) time, O(H) space
    List<Integer> findLeavesDFS(TreeNode root) {
        List<Integer> leaves = new ArrayList<>();
        dfs(root, leaves);
        return leaves;
    }

    private void dfs(TreeNode node, List<Integer> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
            return; // no children to recurse into
        }
        dfs(node.left, leaves);
        dfs(node.right, leaves);
    }

    // BFS: gives leaves level by level, O(N) time, O(W) space
    List<Integer> findLeavesBFS(TreeNode root) {
        List<Integer> leaves = new ArrayList<>();
        if (root == null) return leaves;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left == null && node.right == null) {
                leaves.add(node.val);
                continue;
            }
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return leaves;
    }
}

Pitfalls

• Testing only node.left == null (or only right) instead of both — misclassifies a node with a single child as a leaf.
• Forgetting the null-root base case, causing a NullPointerException on an empty tree.
• Re-traversing the tree once to collect nodes and again to filter leaves — wastes a full pass and O(N) extra memory for no gain over inlining the check.
• Using BFS when the problem needs left-to-right leaf order (e.g. "find leftmost leaf value"): BFS gives level order, not DFS's leaf order, so it silently returns a differently-ordered, wrong-for-this-problem list even though it still "looks" like a valid list of leaves. This is the concrete case where traversal choice is not a free stylistic pick — it determines correctness.

When to use / when not, and trade-offs

Use DFS-based leaf processing by default: it is simpler to write recursively, naturally threads path-dependent state (running sum, depth) through the call stack via parameters, needs only O(H) space — cheaper than BFS's O(W) on any tree that isn't near-perfectly balanced — and is the only safe default when you haven't checked whether the problem is order-sensitive.

Prefer BFS instead when the problem is inherently level-based (e.g. "deepest leaves sum", "leaves at level K") since BFS processes one level at a time by construction, avoiding the need to track depth manually. Avoid BFS when the tree is very wide and shallow (e.g. a nearly complete tree) since its queue can approach O(N/2), worse than DFS's O(H) — and never use BFS when the answer must preserve left-to-right leaf order.

Threading extra "how did I get here" state. Two common variants show why the accumulated parameter, not just the leaf test, is the real work. Sum of Left Leaves (LeetCode 404) needs one more bit than "is this a leaf": it sums a leaf only if it is a left child, so the parent must pass down an isLeftChild flag when it recurses (dfs(node.left, true), dfs(node.right, false)) — a right-only leaf is a leaf but contributes nothing. Leaf-Similar Trees (LeetCode 872) compares two trees by their leaf sequences: run the DFS-left-to-right leaf collection on each, then compare the two lists element-by-element — and this is exactly why order matters, since two trees can share a leaf multiset but differ in leaf sequence.

Vs. Morris traversal (threaded, O(1) space): only worth it if recursion/queue memory is the bottleneck (very large N) — it sacrifices simplicity and temporarily mutates the tree structure, which is a real cost in concurrent or shared-tree contexts.

Takeaways

• Leaf processing = ordinary traversal + a leaf test (left==null && right==null) at each visited node; there is no way to avoid visiting every node, so O(N) time is optimal.
• Traversal order is free to choose only for order-independent aggregates; for order-sensitive outputs (e.g. leftmost leaf, left-to-right leaf list) DFS is required for correctness, not just convenience.
• DFS space is bounded by height H; BFS space is bounded by max width W — pick based on which is smaller for your tree shape, subject to the order constraint above.
• Do the accumulation inline during the single traversal; never collect-then-filter in two passes.

Recall: Why does checking only node.left == null fail to correctly identify leaf nodes?

Synthesized from the original page's DFS/BFS leaf-finding walkthrough, standard binary-tree traversal complexity analysis, and Morris traversal as a space-optimal alternative for interview-style trade-off discussion.