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

You are looking at tree DFS when…

• The question is about a root-to-leaf path — 112, 113, 129, 257.
• It is about a subtree property — 110 balanced, 98 validate BST, 508.
• You need a value computed from children — 104 depth, 543 diameter, 124 max path sum.
• Any path, not necessarily through the root — the split-brain shape.
• “Count paths summing to k” anywhere in the tree — 437, which is DFS plus prefix sums.

Prefer BFS instead for “per level”, “minimum depth”, or “nearest” — see Tree BFS.

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.

treeLC 112: the target travels down, not the running sumchannel 1 · carry state downward

path

5

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))

node5remaining17

descendSubtract 5: 22 − 5 = 17 still to find below 5. Passing the *remaining* target down beats accumulating a running sum — one variable instead of two.

Play‹›1/6⟲

Watch the call stack panel: each frame holds a different remaining target. The leaf 7 fails with remaining 2, the recursion unwinds one frame, and the sibling 2 succeeds against the same remaining 2 -- which is only possible because the state is a parameter, not a shared variable.

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

treeLC 543: what a node RETURNS and what it RECORDS are different numberschannel 2 · summaries upward

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

through0height1best0

combineAt 4: left height 0, right height 0. The longest path *through* 4 uses 0 + 0 = 0 edges, which does not beat 0. But the value returned upward is the height, 1 + max(0, 0) = 1. Keeping those two numbers distinct is the entire difficulty of this problem.

Play‹›1/6⟲

At each node, left + right is a finished path that bends here (recorded), while 1 + max(left, right) is the extendable downward path (returned). Node 2 records 2 and returns 2; the root records 3 and returns 3. Returning the bend value instead is the classic bug -- a parent cannot extend a path that already turned.

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.

has_path_sum.py

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))

A node with one child is not a leaf

The leaf test must be not node.left and not node.right. Testing if not node: return target == 0 instead looks equivalent and is not: on a node with a single child, the missing side would be treated as a complete path and could report a false success.

Concretely, root = [1, 2] with target = 1: the correct answer is False, because the only root-to-leaf path is 1 -> 2 summing to 3. A not node base case returns True, wrongly accepting the empty right side of node 1. This is the most common bug in the whole path-sum family, and it is exactly the same mistake as the LC 111 trap in Tree BFS.

Channel 2 — return summaries upward

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

max_depth.py

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.

collect_paths.py

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

out.append(list(path)) — the copy is mandatory

path is one list mutated throughout the traversal. Appending path itself stores a reference, and every stored “path” is the same object — which pop() then empties. The final answer would be a list of identical empty lists.

list(path) (or path[:], or path.copy()) snapshots the current contents. This is the most common bug in every backtracking problem, not just tree ones.

The matching discipline is that every append has exactly one pop, including on the paths where you recorded a result. In the code above the pop() sits after the if/else, so it runs on every branch.

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.

diameter.py

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.

node	target on entry	leaf?	action
5	22	no	remaining = 22 − 5 = 17, recurse left
4	17	no	remaining = 17 − 4 = 13, recurse left
11	13	no	remaining = 13 − 11 = 2, recurse left
7	2	yes	2 == 7? False — unwind one frame
2	2	yes	2 == 2? True — the or short-circuits all the way up

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.

node	left	right	records left + right	best after	returns 1 + max
4	0	0	0	0	1
5	0	0	0	0	1
2	1	1	2	2	2
3	0	0	0	2	1
1	2	1	3	3	3

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

Approach	Time	Space
Any single-pass tree DFS	$O(n)$	$O(h)$ recursion, h = height
Collecting all root-to-leaf paths	$O(n \cdot h)$	$O(n \cdot h)$ for the output
Iterative with an explicit stack	$O(n)$	$O(h)$ on the heap, no frame limit

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.

Python’s recursion limit

Default limit is 1000 frames. A degenerate tree of 10^4 nodes — which LeetCode’s constraints often allow — will raise RecursionError. Either sys.setrecursionlimit(10**6) or convert to an explicit stack. Worth mentioning unprompted; see Python Recursion and Iterative Conversion.

The variant map

Variant	Channel used	Canonical problem
Does a path exist?	Down (remaining target)	112 Path Sum
Collect all paths	Down + backtracking	113 · 257
Build a number down the path	Down (total * 10 + val)	129 Sum Root to Leaf
Height / depth / balanced	Up (summary)	104 · 110
Any path, may bend	Split-brain	543 · 124 · 687
Count paths summing to k	Down, with a prefix-sum map	437
Validate a subtree property	Up, or down with bounds	98 · 100 · 572

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Subtract as you descend and test at the leaves. Short-circuiting or means the search stops at the first success.

Time $O(n)$. Space $O(h)$.

The two test cases that matter:

• ([], 0) gives False. An empty tree has no root-to-leaf path at all, so even a target of 0 fails. A solution returning True for target == 0 gets this wrong.
• ([1, 2], 1) gives False. Node 1 has only a left child, so the sole path is 1 -> 2 summing to 3. This is the one-child trap described above.

Follow-ups you should expect: “Return all such paths?” — LC 113, next. “Count paths that need not start at the root?” — LC 437: carry a prefix-sum Counter down and decrement it on the way back up, so only the current root-to-node path is in scope. “Do it iteratively?” — an explicit stack of (node, remaining) pairs. “What about negative values?” — fully supported here; note that they rule out any early-exit pruning like “remaining is already negative, give up”.

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 []

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Backtracking on a tree. The shared path list always holds the route from the root to the current node; appending on entry and popping on exit keeps that invariant automatically.

Time $O(n \cdot h)$ in the worst case — $O(n)$ to visit every node, plus $O(h)$ to copy each recorded path. Space $O(h)$ for the recursion and path, plus the output.

Two disciplines make this correct:

1. Copy on record. list(path) — see the caution above.
2. One pop per append, on every branch. Here the pop() is after the if/else, so it executes whether or not a path was recorded. Putting a return inside the if branch without popping first is a classic leak that corrupts every later path.

Note the else: once a matching leaf is found there are no children to recurse into, so the branch is genuinely exclusive. Recursing anyway would still work (both children are None) but the else states the intent.

Follow-ups you should expect: “Return the paths as strings (LC 257)?” — same structure, join with "->". “Paths that need not end at a leaf?” — record at every node instead of only at leaves. “Count instead of collect (LC 437)?” — prefix-sum map with an undo on the way back up; far better than $O(n^2)$ re-walking. “Why not build a new list per recursive call?” — you can (dfs(node.left, remaining, path + [node.val])) and it removes the copy bug, but it allocates $O(h)$ per node instead of once per result.

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The longest path in a tree bends at exactly one node — its highest point. So consider each node as that apex: the best path bending there is height(left) + height(right) edges. Take the maximum over all nodes.

Meanwhile the recursion must return 1 + max(left, right), because a parent can only extend a path that runs straight down.

Time $O(n)$ — one visit per node. Space $O(h)$.

Why edges, not nodes

An empty child returns height 0, so a leaf returns 1 and left + right at a leaf is 0 — correctly, since a single node has diameter 0 edges. [1] giving 0 and [1,2] giving 1 confirm the convention.

If a problem asked for the number of nodes on the path instead, the answer would be best + 1. Read carefully — LC 543 says edges, LC 124 sums values, and LC 687 counts edges of a same-valued path. Same skeleton, three different measurements.

The naive alternative — compute height separately at every node — is $O(n^2)$ because heights get recomputed. Threading the recording through the same single traversal is what makes it linear, and explaining that is the point of the problem.

Follow-ups you should expect: “Maximum path sum (LC 124)?” — same skeleton, but clamp negative contributions with max(0, height(child)) since you may drop a negative branch entirely, and record node.val + left + right. “Longest path with equal values (LC 687)?” — only extend into a child whose value matches. “Return the path itself?” — track the apex node and re-descend from it. “Nodes up to $10^4$ in a chain?” — raise the recursion limit or go iterative.

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.

LC 437 is where two patterns compose

Path Sum III counts downward paths summing to k that may start and end anywhere. The naive answer runs a DFS from every node: $O(n^2)$.

The linear answer is LC 560 — prefix sums plus a hash map — applied along the current root-to-node path. Carry a Counter of prefix sums down the recursion, and decrement your own entry as you return:

python

seen[running] -= 1        # undo before unwinding

Without that undo, prefix sums from a sibling branch leak in and inflate the count. It is the same choose/un-choose discipline as LC 113, applied to a map instead of a list — and it is a genuinely satisfying problem once both pieces are in place.

12 problems

5 easy6 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○94Binary Tree Inorder Traversaleasy
• ○104Maximum Depth of Binary TreeeasyThe plain upward summary: `1 + max(left, right)`NeetCode 150Blind 75LeetCode Top Interview 150
• ○110Balanced Binary TreeeasyReturn the height, or a sentinel `-1` to abort earlyNeetCode 150
• ○112Path SumeasyCarry the remaining target down; a one-child node is not a leafLeetCode Top Interview 150
• ○543Diameter of Binary TreeeasySplit-brain: return the height, record `left + right`NeetCode 150
• ○113Path Sum IImediumBacktracking; copy the path when recording
• ○114Flatten Binary Tree to Linked ListmediumLeetCode Top Interview 150
• ○129Sum Root to Leaf NumbersmediumCarry `total * 10 + val` downwardLeetCode Top Interview 150
• ○437Path Sum IIImediumPrefix-sum map carried down, **decremented** on the way back up
• ○1123Lowest Common Ancestor of Deepest Leavesmedium
• ○1448Count Good Nodes in Binary TreemediumNeetCode 150
• ○124Binary Tree Maximum Path SumhardSplit-brain with negative branches clamped to `0`NeetCode 150Blind 75LeetCode Top Interview 150

Interview follow-ups

They ask	What they’re checking	The answer
“DFS or BFS here?”	Deliberate choice	Paths and subtree properties are DFS; per-level and nearest-thing are BFS
“Why return one value and record another?”	The split-brain insight	A parent can only extend a straight-down path; a bent path is already complete
“Why copy the path?”	Reference vs. value	path is mutated throughout; storing it stores an alias that later pops empty
“Space complexity?”	Precision	$O(h)$ — $O(\log n)$ balanced, $O(n)$ degenerate; the mirror of BFS’s $O(w)$
“What if the tree is 10^4 deep?”	Practical Python	RecursionError at the default limit of 1000; raise it or use an explicit stack
“Count paths not starting at the root?”	Composition	Prefix-sum Counter down the path, decremented on unwind (LC 437)
“Can you avoid recomputing heights?”	Complexity awareness	Thread the recording through one traversal; separate height calls make it $O(n^2)$

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

pch.quizTag Tree DFS paths and sums — self-check

1. Why must the leaf test be `not node.left and not node.right` rather than a `if not node: return target == 0` base case?

   A For speed B Because a node with one child is not a leaf — the missing side would be treated as a complete path, so `[1,2]` with target 1 wrongly returns True C Because the target can be negative D They are equivalent
   pch.quizShowAnswer

   B — Because a node with one child is not a leaf — the missing side would be treated as a complete path, so `[1,2]` with target 1 wrongly returns True — The only root-to-leaf path in [1,2] is 1 → 2 = 3, so the answer is False. This single mistake accounts for most wrong submissions in the path-sum family, and it is the same trap as LC 111's minimum depth.

2. In the diameter solution, why does `height` return `1 + max(left, right)` but record `left + right`?

   A To save a variable B Because they are different things: left + right is a path that bends here and is finished, while 1 + max(left, right) is the extendable downward path a parent can build on C Because the diameter is measured in nodes, not edges D Because max is faster than addition
   pch.quizShowAnswer

   B — Because they are different things: left + right is a path that bends here and is finished, while 1 + max(left, right) is the extendable downward path a parent can build on — Returning the bend value produces nonsense, because a parent cannot extend a path that already turned. This exact split solves LC 543, 124, 687 and 1522.

3. `out.append(path)` instead of `out.append(list(path))` in the path-collecting template. What is the result?

   A A shallow-copy warning B Every stored 'path' is a reference to the same list, which the un-choose `pop()` then empties — the answer is a list of identical empty lists C Only the last path is wrong D It works but is slower
   pch.quizShowAnswer

   B — Every stored 'path' is a reference to the same list, which the un-choose `pop()` then empties — the answer is a list of identical empty lists — The copy snapshots the current contents. This is the most common bug in all of backtracking, not just tree problems, and it is why every append must be paired with exactly one pop.

4. Which channel should carry the state for 'does a root-to-leaf path sum to target'?

   A Upward: return the sum of each subtree and compare at the root B Downward: pass the remaining target as a parameter, so each recursive call gets its own copy and no undo is needed C A global running total D Either, they are equally clean
   pch.quizShowAnswer

   B — Downward: pass the remaining target as a parameter, so each recursive call gets its own copy and no undo is needed — In the dry run two sibling leaves both see remaining = 2 and disagree — safe because the state is a parameter. A shared accumulator would need an explicit undo on the way back up.

5. What is the space complexity of the recursive traversal, and why does it matter in Python specifically?

   A O(1); it does not matter B O(h) stack frames — O(n) on a degenerate tree — and CPython's default limit is ~1000 frames, so a 10^4-node chain raises RecursionError C O(n) always D O(w), the width of the widest level
   pch.quizShowAnswer

   B — O(h) stack frames — O(n) on a degenerate tree — and CPython's default limit is ~1000 frames, so a 10^4-node chain raises RecursionError — O(w) is BFS's bound; DFS is O(h). LeetCode constraints routinely allow 10^4 nodes, so either raise the limit or convert to an explicit stack — and say so before being asked.

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.