Tree Paths

1. Introduction: Tracing the Branches

A massive portion of Binary Tree questions revolve around Paths. A path is a continuous sequence of nodes from one node to another.

Path problems test your ability to carry "state" (like a running sum or a list of nodes) down the branches of a tree using recursion, and your ability to bubble results back up. There are two main categories of path problems:

1. Root-to-Leaf Paths: Strict vertical paths starting at the very top and ending strictly at a leaf node (a node with no children).
2. Any-to-Any Paths: A path can start anywhere, go up to a common ancestor, and go down another branch. (These are usually Hard difficulty).

2. Core Concept: Root-to-Leaf Backtracking

When tracking a path from the root to a leaf, you pass a variable (e.g., currentSum or List<Integer> currentPath) down as a parameter in your recursive function.

If you pass a primitive int, Java passes it by value. Every recursive stack frame gets its own isolated copy of the sum. But if you pass an Object (like a List), Java passes the reference. All branches share the same List in memory. If the left branch adds a node, the right branch will see it! You MUST remove the node after the recursive call finishes. This is called Backtracking.

3. Beginner Code Example: Path Sum I

Problem Statement: (LeetCode 112) Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

The Insight: As we travel down, we subtract the current node's value from the targetSum. When we hit a leaf, we check if the remaining targetSum exactly equals the leaf's value!

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class PathSum {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Base case: Hit a null node (not a leaf, just an empty space)
        if (root == null) {
            return false;
        }
        
        // Base case: True LEAF node!
        if (root.left == null && root.right == null) {
            // Did the running subtraction hit zero exactly?
            return targetSum == root.val;
        }
        
        // Recursive Step: Subtract current value and ask left OR right branches
        boolean leftBranch = hasPathSum(root.left, targetSum - root.val);
        boolean rightBranch = hasPathSum(root.right, targetSum - root.val);
        
        return leftBranch || rightBranch;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. In the worst case, we check every node once.
• Space Complexity: $O(H)$ where $H$ is the height of the tree (for the recursion stack).

4. Intermediate Code Example: Path Sum II (Backtracking)

Problem Statement: (LeetCode 113) Given the root and targetSum, return all root-to-leaf paths where the sum equals targetSum. Return the paths as lists of integers.

The Insight: We must carry a currentPath list down the tree. Because lists are passed by reference, we must add the node before recursing, and remove it immediately after recursing. When we find a valid path, we must make a Deep Copy of the list to save it in our results.

import java.util.ArrayList;
import java.util.List;

public class PathSumII {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, targetSum, new ArrayList<>(), result);
        return result;
    }
    
    private void dfs(TreeNode node, int targetSum, List<Integer> currentPath, List<List<Integer>> result) {
        if (node == null) return;
        
        // 1. ACTION: Add current node to the path
        currentPath.add(node.val);
        
        // 2. CHECK: If it's a leaf and the sum matches
        if (node.left == null && node.right == null && targetSum == node.val) {
            // CRITICAL: Make a deep copy!
            result.add(new ArrayList<>(currentPath));
        } else {
            // 3. RECURSE: Continue down the tree
            dfs(node.left, targetSum - node.val, currentPath, result);
            dfs(node.right, targetSum - node.val, currentPath, result);
        }
        
        // 4. BACKTRACK: Remove the current node before returning to the parent
        // This ensures the parent's other branches don't inherit this branch's nodes!
        currentPath.remove(currentPath.size() - 1);
    }
}

5. Advanced Code Example: Binary Tree Maximum Path Sum

Problem Statement: (LeetCode 124) Find the maximum path sum of any non-empty path. The path may start and end at ANY node in the tree (it does not have to go through the root, nor does it have to end at a leaf).

This is a notorious FAANG Hard problem. The Insight: A path that curves over a node (looks like an inverted V) cannot be extended upwards to the node's parent. It is a "closed" path. Therefore, at every node, our recursive function must do two things:

1. Calculate the inverted-V path that curves through the current node. Update a global maxSum.
2. Return a straight-line path (either Left branch + Node, or Right branch + Node) upwards to the parent so the parent can build its own paths.

public class MaxPathSum {
    // Global variable to track the absolute maximum inverted-V path we've seen
    private int globalMax = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return globalMax;
    }
    
    // Returns the maximum "straight line" path starting from this node downwards
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        
        // 1. Get the max straight-line paths from left and right children.
        // We use Math.max(0, ...) to ignore paths with negative sums! 
        // (A negative path actively hurts our total, so we just pretend it doesn't exist).
        int leftMax = Math.max(0, dfs(node.left));
        int rightMax = Math.max(0, dfs(node.right));
        
        // 2. Calculate the "Inverted-V" path passing THROUGH the current node
        int currentInvertedV = node.val + leftMax + rightMax;
        
        // 3. Update the global maximum if this V-path beats our previous record
        globalMax = Math.max(globalMax, currentInvertedV);
        
        // 4. Return the maximum STRAIGHT LINE path to the parent
        // The parent can only attach to one of our branches!
        return node.val + Math.max(leftMax, rightMax);
    }
}

6. Common Mistakes Beginners Make

1. Confusing null nodes with Leaf nodes

   • The Mistake: In Root-to-Leaf path checks, writing if (root == null && targetSum == 0) return true;.
   • Why it's wrong: If a node has a left child but no right child, calling hasPathSum(root.right) hits the null node. It returns true, completely ignoring the fact that the path didn't end at a true leaf! A leaf must explicitly be node.left == null && node.right == null.

2. Forgetting to Backtrack the List

   • The Mistake: Not calling currentPath.remove() at the end of the dfs function.
   • Why it's wrong: The currentPath is a single object in memory. If you traverse the left side of the tree and don't clean up, when you start traversing the right side of the tree, all the left-side nodes are still sitting in your list! Your output will be garbage.

3. Not Deep Copying the Path

   • The Mistake: result.add(currentPath);
   • Why it's wrong: You added a reference to the list. When your backtracking eventually removes all elements from the list, the list inside your result array will also become empty. You will end up with [[], [], []]. Use new ArrayList<>(currentPath).

7. Interview Q&A

Q1: How do you solve "Path Sum III" (LeetCode 437) where paths can start and end anywhere going downwards? Answer: This requires Prefix Sum Hashing, exactly like we do in 1D Arrays! You pass a HashMap<Integer, Integer> down the recursion tracking the running prefix sums. At any node, if currentSum - targetSum exists in the map, you found a valid sub-path! Don't forget to backtrack by removing the currentSum from the map before returning to the parent.

Q2: What is the Time Complexity of Path Sum II (saving all paths)? Answer: While exploring the tree is $O(N)$, generating a deep copy of a path takes $O(H)$ time where $H$ is the height. If the tree is highly balanced and almost every path is valid, the time complexity can degrade to $O(N \log N)$ or even $O(N^2)$ in degenerate trees.

8. Practice Problems

1. Path Sum (LeetCode 112)
   • Goal: Perfect the Leaf node check and boolean || bubbling.
2. Path Sum II (LeetCode 113)
   • Goal: Master Backtracking and Deep Copying on a shared List.
3. Binary Tree Maximum Path Sum (LeetCode 124 - Hard)
   • Goal: Master the dual-responsibility DFS (update global V-path, return local straight-path).

9. Summary

• State Passing: Primitives (int) are isolated per frame. Objects (Lists) are shared and require backtracking.
• Leaf Definition: if (node.left == null && node.right == null).
• Backtracking Rule: Action $\rightarrow$ Recurse $\rightarrow$ Undo Action.
• Deep Copy Rule: result.add(new ArrayList<>(path));