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

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

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

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. 9898 (validate BST), 110110 (balanced), and 104104 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

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

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 + rightleft + right is a path through this node that is finished. 1 + max(left, right)1 + max(left, right) is what the parent can build on. Conflating them — returning left + rightleft + 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.

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 variant map

Practice — real LeetCode problems

LC 112 — Path Sum · Easy

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

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

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

LC 113 — Path Sum II · Medium

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

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

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

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^41 <= number of nodes <= 10^4, -100 <= Node.val <= 100-100 <= Node.val <= 100.

Examples. [1,2,3,4,5][1,2,3,4,5] gives 33 (the path 4 -> 2 -> 1 -> 34 -> 2 -> 1 -> 3) · [1,2][1,2] gives 11 · [1][1] gives 00

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Empty tree — LC 112 must return FalseFalse even for targetSum = 0targetSum = 0.
• Single node — diameter 00; a path sum equal to that node’s value is TrueTrue.
• One-child nodes — [1,2][1,2] with target 11 is FalseFalse. 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, ...)max(0, ...) clamp in LC 124.
• Target sum of zero — valid; do not treat 00 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][1,2,3,4,null,null,5,6,null,null,7] has diameter 66, and no path through the root achieves it.

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 nodeif 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)list(path), never pathpath. Every appendappend needs exactly one poppop, on every branch.
• The split-brain trick — return 1 + max(left, right)1 + max(left, right), record left + rightleft + 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.