Tree DFS Paths and Sums

Tree BFS answers questions about levels. Tree DFS answers questions about paths and subtrees -- and the reason is structural: recursion naturally gives you two channels of information that BFS does not.

Down the recursion you carry context: the path so far, the remaining target, the accumulated number. Up the recursion you return summaries: a height, a subtree sum, a best-so-far.

Almost every tree DFS problem is a question of which channel you need. Get that right and the code writes itself.

What you'll learn

• The two information channels, and how to decide which a problem wants.
• The choose / recurse / un-choose discipline for collecting paths, and why you must copy the path when you record it.
• The split-brain trick: when the value you return differs from the value you record. This is the single most reusable idea on the page.
• Why a node with one child is not a leaf, and where that bites.
• Three real LeetCode problems solved in the browser: 112, 113, 543.

The cue

Visual intuition

The two channels, one per trace. First downward state: the target shrinks on the way down, and the leaf test is a comparison against what is left.

1def has_path_sum(node, target):2    if node is None:3        return False4    target -= node.val5    if node.left is None and node.right is None:6        return target == 0          # leaf: exact match?7    return (has_path_sum(node.left,  target) or8            has_path_sum(node.right, target))

Now upward summaries, and the split-brain structure that solves every "any path, not necessarily through the root" problem:

1def diameter(root):2    best = 03    def height(node):4        nonlocal best5        if node is None: return 06        l = height(node.left)7        r = height(node.right)8        best = max(best, l + r)     # path THROUGH this node9        return 1 + max(l, r)        # height reported UP10    height(root)11    return best

Channel 1 — carry state downward

Pass what the child needs as an argument. For path problems that is usually the remaining target, which is cleaner than accumulating a running total and comparing at the bottom.

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:        # a real leaf
        return target == root.val
    remaining = target - root.val
    return (has_path_sum(root.left, remaining)
            or has_path_sum(root.right, remaining))

Channel 2 — return summaries upward

When the answer depends on children, compute both sides first, then combine.

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

That is the whole shape: base case for the empty tree, recurse both sides, combine. 98 (validate BST), 110 (balanced), and 104 are all this with a different combine step.

Collecting paths — choose / recurse / un-choose

To record paths rather than just test them, maintain one shared list and undo your change on the way out. This is backtracking applied to a tree.

def path_sum(root, target):
    out, path = [], []
 
    def dfs(node, remaining):
        if not node:
            return
        path.append(node.val)                              # choose
        if not node.left and not node.right and remaining == node.val:
            out.append(list(path))                         # COPY, not path
        else:
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)
        path.pop()                                         # un-choose
 
    dfs(root, target)
    return out

The split-brain trick

Here is the idea worth taking away. Some problems ask about paths that do not pass through the root -- diameter, maximum path sum. The trick is that the recursion returns one thing while a side channel records another:

• Return the best path that goes downward from this node, because that is all a parent can extend.
• Record the best path that bends at this node (left side + right side), because that path is complete and cannot be extended upward.

def diameter(root):
    best = 0
 
    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)      # RECORD: path bending here
        return 1 + max(left, right)         # RETURN: extendable downward path
 
    height(root)
    return best

Those two lines are different on purpose. left + right is a path through this node that is finished. 1 + max(left, right) is what the parent can build on. Conflating them -- returning left + right -- produces nonsense, because a bent path cannot be extended by a parent.

This exact structure solves LC 543, LC 124, LC 687, LC 1522 and more. Once you recognise "any path, not necessarily through the root", you write these two lines and fill in the details.

Dry run

Channel 1 — has_path_sum on [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22. Only the left spine is shown, because that is where the answer is found.

Path 5 → 4 → 11 → 2 sums to 22. ✓

• Two leaves see the same remaining = 2 and disagree. That only works because the state is a parameter: the failing call at leaf 7 cannot corrupt what leaf 2 receives. A shared self.running_total would need an explicit undo, which is the bug this channel exists to avoid.
• The or is the pruning. Once leaf 2 returns True, has_path_sum(root.right, …) is never called — the entire right subtree, node 8 and below, goes unvisited.
• The leaf test is what makes it correct. Try root = [1, 2], target = 1: the only root-to-leaf path is 1 → 2 = 3, so the answer is False. With a if not root: return target == 0 base case, node 1's missing right child returns True and the function wrongly succeeds.

Channel 2 — diameter on [1,2,3,4,5]. Post-order, so children resolve first. best is the side channel.

Diameter 3 — the path 4 → 2 → 1 → 3, which has 3 edges and does not pass through any single node as an endpoint.

• At node 2 the recorded and returned values coincide (both 2) and at the root they do not (records 3, returns 3 — equal here by coincidence of shape, but the meanings differ: 3 edges bending at the root versus a 3-node downward chain). Node 2 is the one to check when debugging: left + right = 2 is the finished path 4 → 2 → 5, while 1 + max(1,1) = 2 is what node 1 may extend.
• The answer is never the return value. height(root) is discarded; best is returned. Every problem in this family has that shape, and returning the recursion's value instead is the fastest way to a wrong answer that still compiles.

Complexity

Space is $O(\log n)$ for a balanced tree and $O(n)$ for a degenerate one -- the mirror image of BFS, which is $O(w)$ in the widest level.

The $O(n \cdot h)$ for collecting paths is worth stating separately, because it is a different bound from testing one: each of up to $n/2$ leaves copies a path of length up to $h$. The copy is mandatory (see the caution above), so this cost is unavoidable — but it is the output size, not wasted work.

The variant map

Practice -- real LeetCode problems

LC 112 -- Path Sum · Easy

Problem. Given the root of a binary tree and an integer targetSum, return True if there is a root-to-leaf path whose values sum to targetSum.

Constraints. 0 <= number of nodes <= 5000, -1000 <= Node.val <= 1000.

Examples. [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 gives True (5 -> 4 -> 11 -> 2) · [1,2,3], targetSum = 5 gives False · [], targetSum = 0 gives False

Press Run to see what your code prints.

LC 113 -- Path Sum II · Medium

Problem. Return all root-to-leaf paths whose values sum to targetSum. Each path is returned as a list of node values.

Constraints. 0 <= number of nodes <= 5000, -1000 <= Node.val <= 1000.

Examples. [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 gives [[5,4,11,2],[5,8,4,5]] · [1,2,3], targetSum = 5 gives []

Press Run to see what your code prints.

LC 543 -- Diameter of Binary Tree · Easy

Problem. The diameter is the length of the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

Constraints. 1 <= number of nodes <= 10^4, -100 <= Node.val <= 100.

Examples. [1,2,3,4,5] gives 3 (the path 4 -> 2 -> 1 -> 3) · [1,2] gives 1 · [1] gives 0

Press Run to see what your code prints.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

Interview follow-ups

Edge-case checklist

• Empty tree -- LC 112 must return False even for targetSum = 0.
• Single node -- diameter 0; a path sum equal to that node's value is True.
• One-child nodes -- [1,2] with target 1 is False. The defining trap of this family.
• Negative node values -- legal; they forbid pruning on "the remaining target went negative", and they force the max(0, ...) clamp in LC 124.
• Target sum of zero -- valid; do not treat 0 as "no target".
• Deep degenerate tree -- recursion limit; mention it before it bites.
• Duplicate values -- never identify nodes by value; use the node objects.
• Path bending away from the root -- [1,2,3,4,null,null,5,6,null,null,7] has diameter 6, and no path through the root achieves it.

Self-check

Recall card

• Cue — a question about paths, sums, depths or bends in a binary tree. Ask first: does a child need something from above, or does a parent need something from below?
• Channel 1, downward — pass what the child needs as a parameter, usually the remaining target. No undo needed, because each call owns its copy.
• Channel 2, upward — recurse both sides, then combine. max_depth, validate, balanced are all this with a different combine step.
• Leaf test — not node.left and not node.right. A one-child node is not a leaf; that is the family's defining bug.
• Collecting paths — choose / recurse / un-choose, with one pop per append, and out.append(list(path)) — the copy is mandatory.
• Split-brain (any path, not through the root) — record left + right (bends here, finished), return 1 + max(left, right) (extendable). The answer is the side channel, never the return value.
• Cost — $O(n)$ time, $O(h)$ stack; $O(n \cdot h)$ when the output is every path. Mention Python's ~1000-frame limit on degenerate trees.

Recap

• Tree DFS gives you two channels: carry context down as arguments, return summaries up. Deciding which the problem needs is most of the work.
• A leaf has neither child. Using if not node as the leaf test wrongly accepts the missing side of a one-child node -- the single most common bug here.
• To collect paths, choose / recurse / un-choose, and record list(path), never path. Every append needs exactly one pop, on every branch.
• The split-brain trick -- return 1 + max(left, right), record left + right -- solves the whole "any path, may bend" family in two lines.
• $O(n)$ time and $O(h)$ space; watch Python's 1000-frame recursion limit on degenerate trees.
• DFS composes with other patterns: LC 437 is this page plus prefix sums and a hash map.

Next: BST Patterns -- what changes once the tree is ordered, and why an in-order walk is often the entire solution.