Pathfinding Algorithms

1. Path Sum I: Does a Valid Path Exist?

Let's start with the foundational problem: given a binary tree and a targetSum, determine if there is a root-to-leaf path where adding up all the values along the path equals the targetSum.

A leaf node is a node with no children. A root-to-leaf path must start at the root and end at a leaf.

The most direct way to solve this is with Depth-First Search (DFS). The core idea is to traverse from the root downwards, keeping track of the sum needed to reach our target. At each node, we subtract its value from the sum we're looking for and pass this new, smaller target to its children.

Let's watch a video that explains this approach and its implementation.

The Recursive Logic Deconstructed

To solidify the pattern, let's break down the logic of the recursive helper function, which we can call dfs(node, remaining_sum).

1. Base Case (Termination): If node is None, it means we've gone past a leaf. This path is invalid, so we return False.
2. Update State: We subtract the current node's value from the sum we need: remaining_sum -= node.val.
3. Goal Check (Leaf Node): This is the most critical step. If the current node is a leaf (node.left is None and node.right is None), we check if our remaining_sum is now exactly 0. If it is, we've found a valid path, and we return True.
4. Recursive Step (Internal Node): If it's not a leaf, we continue the search. We need to find a valid path in either the left subtree OR the right subtree. We make two recursive calls: dfs(node.left, remaining_sum) and dfs(node.right, remaining_sum). The logical or combines their results.

This approach elegantly explores all root-to-leaf paths. The recursive call stack naturally handles the "backtracking" for us.

For a more detailed written explanation and a discussion of common mistakes, the following resource is excellent.

2. Path Sum II: Finding All Valid Paths

Now for a common and slightly more complex variation. Instead of just returning True or False, we need to return a list of all root-to-leaf paths that sum up to the target.

This changes the problem significantly:

• We can't stop after finding the first valid path.
• We need to keep track of the actual nodes in the current path.
• This requires explicit backtracking.

The core idea is still DFS, but we'll add a list to our function's state to build the path as we go. The backtracking pattern is: Choose, Explore, Unchoose.

1. Choose: When we visit a node, we add it to our current path list.
2. Explore: We make recursive calls for its children.
3. Unchoose: After the recursive calls for a node's children have returned, we must remove that node from our path list. This "unchoosing" is the backtracking step. It ensures that when we explore a sibling branch, the path is restored to its correct state.

The following video demonstrates this pattern.

The Backtracking Pattern in Detail

Let's dig into the two trickiest parts of this implementation, which are essential for any problem that involves collecting path results.

As the article highlights, there are two crucial details:

1. Path Copying: When you find a valid path at a leaf node, you must add a copy of the current path to your results list (e.g., result.append(list(path)) in Python). If you just appended path itself, all entries in your result list would point to the same object, which you will continue to modify, leading to an incorrect final answer.
2. Backtracking with pop(): The line path.pop() (or its equivalent) after the recursive calls is the heart of backtracking. It cleans up the state, ensuring that the path is correct for explorations in other parts of the tree.

Here is a Python implementation template that follows this pattern:

def pathSum(root, targetSum):
    result_paths = []
    current_path = []

    def dfs(node, remaining_sum):
        if not node:
            return

        # 1. Choose: Add the current node to the path
        current_path.append(node.val)

        # 2. Goal Check: At a leaf, check if the path is a solution
        if not node.left and not node.right and remaining_sum == node.val:
            result_paths.append(list(current_path)) # Add a copy!
        
        # 3. Explore: Recurse on children
        dfs(node.left, remaining_sum - node.val)
        dfs(node.right, remaining_sum - node.val)

        # 4. Unchoose: Backtrack by removing the current node from the path
        current_path.pop()

    dfs(root, targetSum)
    return result_paths

Conclusion

Excellent work! You've just learned one of the most fundamental patterns for solving tree problems. By mastering these two "Path Sum" variations, you've equipped yourself with a powerful template that applies to many other interview questions.

Key Takeaways:

• DFS for Paths: DFS is the go-to algorithm for path-finding problems in trees, as it naturally explores paths from root to leaf.
• Passing State Down: Unlike the property problems from our last lesson, path-finding often involves passing state (like a remaining_sum) down the recursion.
• Path Sum I (Existence): Use a simple recursive DFS. A leaf node check is critical, and results from subtrees are combined with a logical or.
• Path Sum II (Collecting): This requires the full backtracking pattern (Choose -> Explore -> Unchoose). Remember to manage a current_path list, pop() to backtrack, and add a copy of the path to your results.

In our next lesson, we will tackle another classic problem that builds on tree traversals: serializing a binary tree to a string and deserializing it back. This is a common design-style question in interviews and a great test of your traversal knowledge.