Backtracking Field Notes

0Why backtracking exists

Backtracking is a brute-force method: try every possible solution, and the moment a partial attempt hits a dead end, undo the last step and try the next option. It overlaps a lot with DFS (depth-first search): you go as deep as you can before you turn around. The new part is the undo. You keep a record of the choices made so far, and when a branch fails you remove those choices before trying the next branch.

Two words you will meet on every backtracking problem. A choice is one option at a fork (go left, go right, take this number, skip it). A dead end is a partial attempt that can no longer become a valid answer. Detecting dead ends early is called pruning; it is what separates backtracking from blindly listing everything.

1The motivating problem: reach a leaf without a 0

The question

Given a binary tree, determine if there exists a path from the root to a leaf (a node with no children) such that no node on the path has value 0. Return True if such a path exists, else False. A node with value 0 is a wall in the maze: you cannot walk through it.

The reasoning, step by step

Use DFS. The constraint is "no node with value 0". Work out the small cases first, then the recursive case.

• Empty tree (root is None): there is no path at all, so return False. Note that NeetCode writes null; in Python it is None.
• Node value is 0: this branch is blocked, return False.
• Reached a leaf (and it is not 0): we walked root-to-leaf without touching a 0, return True.
• Otherwise: if a solution exists, it is in the left subtree or the right subtree.

1. Arbitrarily explore the left subtree first.
2. If left returns True, return True.
3. If left returns False, explore the right subtree.
4. If right returns True, return True.
5. If both return False, return False.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def canReachLeaf(root):
    if not root or root.val == 0:      # empty, or a wall: dead end
        return False

    if not root.left and not root.right:   # a leaf, and it is not 0: found a path
        return True
    if canReachLeaf(root.left):           # try left first (arbitrary choice)
        return True
    if canReachLeaf(root.right):          # left failed, try right
        return True
    return False                          # both failed: this node is a dead end

The lesson's example: [4,0,1,null,7,2,0]

Root 4. Its left child is 0, and that 0 has a right child 7. Its right child is 1, with children 2 and 0. A path is invalid if it contains a 0. The only valid root-to-leaf path is 4 → 1 → 2.

2Variation: also build the path

The question

Same rule, but now return the path itself: the node values from root to leaf, in the order they were visited. We pass a parameter path (a Python list) into the recursion. Every call that is on a promising branch appends its value. Every call that turns out to be a dead end removes its value again before returning. That removal is the backtrack.

def leafPath(root, path):
    if not root or root.val == 0:
        return False
    path.append(root.val)                # choose: this node is on the path (for now)

    if not root.left and not root.right:
        return True                      # leaf: keep it in the path, done
    if leafPath(root.left, path):        # explore left
        return True
    if leafPath(root.right, path):       # explore right
        return True
    path.pop()                           # un-choose: no valid path goes through here
    return False

Call it with an empty list: path = []; leafPath(root, path). When the function returns True, path holds the answer. When it returns False, path is empty again, because every append was matched by a pop.

The lesson's example: [4,0,1,null,7,3,2,null,null,null,0]

Root 4. Left child 0 with a right child 7. Right child 1 with children 3 and 2. Node 3 has a right child 0. This tree is chosen so that one branch (through 3) looks promising, gets added to the path, and then must be removed.

The path list, moment by moment

The lesson describes nine steps. Here they are, and under them the exact state of path after each one.

1. Add root 4 to the list. path = [4].
2. Left subtree is invalid (4's left child is 0), so that call returns False. Check the right subtree.
3. 1 is valid: add it. path = [4, 1].
4. 3 is valid: add it. path = [4, 1, 3].
5. 3's left child is None: return False.
6. 3's right child is 0: base case, return False.
7. Remove 3 from the list (pop). If a valid path went through 3 we would have returned True already. path = [4, 1].
8. Back up to 3's parent, node 1, and check its right subtree.
9. Add 2. 2 is a leaf, so return True, and the whole function returns True. path = [4, 1, 2].

Full trace of leafPath on this tree

Each row is one event inside the recursion. "Path after" is the list at that moment. Read it top to bottom and match the circled numbers with the tree figure above.

3Time and space

Time: O(n)

In the worst case there is no valid path, or the only one is in the last branch, and the recursion visits every node once. Each visit does constant work (a few comparisons, one append, one pop). So the total is O(n), where n is the number of nodes. Nodes below a 0 are skipped, so the real count is often smaller, but Big-O reports the worst case.

Space: O(h)

Two things use memory, and both are bounded by the height h of the tree (the longest root-to-leaf distance). First, the call stack: recursion goes at most h levels deep, because each call moves one level down. Second, the path list: it holds one value per active call that appended, so it never holds more than h + 1 values at once. The rejected values are popped before the list can grow further.

The lesson closes with this: backtracking is a common pattern and it applies far beyond binary trees. Subsets, permutations, and combinations are the classic examples and they are covered in later lessons and courses. The next section shows that the exact same three lines drive all of them.

4Moves that solve most backtracking problems

leafPath already contains the whole template. Pull it out and you can reuse it on problems that have nothing to do with trees.

Move 1: The universal loop, choose → explore → un-choose

Every backtracking function has the same body. Make a choice and record it. Recurse to explore what follows from that choice. When the recursion returns, undo the choice so the next option starts from a clean state.

def backtrack_template(candidates):
    # records every ordered selection of distinct items, to show the shape
    res, choice = [], []

    def explore():
        res.append(list(choice))          # record the current state
        for c in candidates:
            if c in choice:
                continue                  # prune: this option is not allowed
            choice.append(c)              # 1. choose
            explore()                     # 2. explore
            choice.pop()                  # 3. un-choose
    explore()
    return res

backtrack_template([1, 2])   # [[], [1], [1, 2], [2], [2, 1]]

When to use: the problem says "all", "every", "generate", "enumerate", or asks whether any arrangement satisfies a rule, and the input is small (n ≤ about 20). The three questions to answer before you code: what are the choices at each step, when is a partial state a dead end (prune), and when is a state a complete answer (record it)?

Move 2: Subsets (take it or skip it)

For each element you make a two-way choice: include it or not. That gives a binary decision tree with 2ⁿ leaves, one per subset. There is no dead end here; every leaf is an answer, so no pruning is needed.

def subsets(nums):
    res, cur = [], []

    def dfs(i):
        if i == len(nums):
            res.append(cur[:])            # copy! cur keeps changing after this
            return
        cur.append(nums[i])               # choose: take nums[i]
        dfs(i + 1)
        cur.pop()                         # un-choose
        dfs(i + 1)                        # other choice: skip nums[i]
    dfs(0)
    return res

subsets([1, 2])       # [[1, 2], [1], [2], []]
len(subsets([1, 2, 3]))   # 8

When to use: "all subsets", "all combinations of any size", or any problem where each item is independently in or out.

Move 3: Permutations (a used array is the choose / un-choose)

Order matters and every element must appear exactly once. At each level try every element that is not used yet. The used list is the state you must undo.

def permutations(nums):
    res, cur, used = [], [], [False] * len(nums)

    def dfs():
        if len(cur) == len(nums):
            res.append(cur[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue                  # prune: already in cur
            used[i] = True                # choose
            cur.append(nums[i])
            dfs()                         # explore
            cur.pop()                     # un-choose (both changes!)
            used[i] = False
    dfs()
    return res

permutations([1, 2, 3])
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

When to use: "all orderings", "arrangements", or anything where [1,2] and [2,1] count as different answers. n! answers, so n is always small.

Move 4: Combinations (a start index stops duplicates)

Choose k numbers out of 1..n where order does not matter. To avoid producing both [1,2] and [2,1], each call only looks at numbers larger than the last one chosen. That is the start parameter.

def combinations(n, k):
    res, cur = [], []

    def dfs(start):
        if len(cur) == k:
            res.append(cur[:])
            return
        for i in range(start, n + 1):
            cur.append(i)                 # choose
            dfs(i + 1)                    # explore only larger numbers
            cur.pop()                     # un-choose
    dfs(1)
    return res

combinations(4, 2)   # [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

When to use: "choose k of n", "combination sum", "pick a team". If elements may be reused (Combination Sum), recurse with dfs(i) instead of dfs(i + 1).

Move 5: Collect every path (Path Sum II shape)

leafPath stops at the first answer. Interview problems usually want all of them. Two changes: never return early, and record a copy of the path at each leaf. Because nothing returns early, the pop happens on every exit, so the un-choose can move to the end of the function.

def allLeafPaths(root):
    res, path = [], []

    def dfs(node):
        if not node or node.val == 0:
            return
        path.append(node.val)             # choose
        if not node.left and not node.right:
            res.append(path[:])           # record a copy, keep going
        else:
            dfs(node.left)                # explore both, always
            dfs(node.right)
        path.pop()                        # un-choose on every exit
    dfs(root)
    return res

# tree [1,2,3,4,5,null,6] → [[1,2,4], [1,2,5], [1,3,6]]
# the lesson's trees → [[4,1,2]]

Backtracking or dynamic programming?

Both explore choices recursively, so beginners mix them up. The decision comes from what the question asks for.

Test for repeated subproblems: does the answer for the rest of the input depend only on a small state (index, remaining sum) and not on the exact choices made so far? If yes, DP. If the whole path matters (N-Queens, Sudoku, "print all paths"), backtracking.

5Big-O summary

For enumeration problems the output itself is huge, so the time is "number of answers × cost to build one". Say that sentence in the interview; it shows you know where the cost comes from.

The asterisk on allLeafPaths: the visit is O(n), and the O(n · h) is a loose bound for the copying, since a tree has at most n leaves. "Extra space" means the recursion stack and the working list, not the returned answers. Interviewers usually ask "excluding the output"; say which one you mean.

6Mistakes to watch for

7Practice, in this order

The first three are the lesson's problem in LeetCode clothing. Then the three classic enumerations, then the ones that add pruning and a grid. Do them without notes, then compare with the templates above.

Your next step today: LeetCode 257. Write allLeafPaths from memory, then change it to return only the first path and check that the pop moves back to the failure branch.

8Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.