Binary Tree Path Sum - Find all paths between any two nodes

Problem

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root.

Examples

Example 1:

       10
     /    \
    7      15
  /  \    /  \
 8    9  11   1

Input: root = [10, 7, 15, 8, 9, 11, 1], targetSum = 16
Output: [ [7,9], 15,1 ]
Explanation:
We have 2 paths with sum equal to 16:
7 - 9 - null
15 - 1 - null

Solution

Method 1 - Backtracking

To solve this problem, we need to design an algorithm that can find all paths in a binary tree that sum up to a given value. The paths can begin and end at any node in the tree.

Approach

1. DFS Traversal: Use Depth-First Search (DFS) to traverse each node.
2. Path Tracking: Keep track of the path from the root to the current node.
3. Subpath Sums: For each node, check all possible subpaths ending at that node to see if they sum up to the given target value.
4. Backtracking: Ensure that after exploring a node, we backtrack to explore other possible paths.

We do DFS with following cases:

1. Base case - If the node is null, return.
2. Path Tracking: Add the current node to the path.
3. Subpath Sums: Iterate backward through the current path and calculate the sum of subpaths ending at the current node. If any subpath sums up to the target, add it to the result.
4. Recursive Calls: Recursively explore the left and right subtrees.
5. Backtracking: Remove the last node from the current path after exploring both subtrees.

Code

Java

public class Solution {

	public List < List<Integer>> pathSum(TreeNode root, int targetSum) {
		List < List<Integer>> ans = new ArrayList<>();
		List<Integer> currPath = new ArrayList<>();
		dfs(root, sum, currPath, ans);
		return ans;
	}

private void dfs(TreeNode node, int target, int currSum, List<Integer> currPath, List <List<Integer>> ans) {
		if (node == null) {
			return;
		}
		// Add the current node to the path
		currPath.add(node.val);
		int newSum = currSum + node.val;

		if (newSum == target) {
			ans.add(new ArrayList<>(currPath));
		}

		// Recursively search the left and right subtrees
		dfs(node.left, target, newSum, currPath, ans);
		dfs(node.right, target, newSum, currPath, ans);

		// Backtrack by removing the current node from the path
		currPath.remove(currentPath.size() - 1);
	}

}

Python

class Solution:
    def pathSum(self, root, target):
        def dfs(node, current_path):
            if not node:
                return
            
            # Add current node to the path
            current_path.append(node.val)
            
            # Check for valid paths that end at current node
            running_sum = 0
            for i in range(len(current_path) - 1, -1, -1):
                running_sum += current_path[i]
                if running_sum == target:
                    result.append(current_path[i:])
            
            # Recur for left and right children
            dfs(node.left, current_path)
            dfs(node.right, current_path)
            
            # Backtrack: remove the current node from the path
            current_path.pop()
        
        result = []
        dfs(root, [])
        return result

Complexity

• ⏰ Time complexity: O(2^n), where n is tree size, as in recursion, we split into 2 trees, hence we have to make a choice into 2 branches, hence 2^n.
• 🧺 Space complexity: O(n) due to the path list and call stack in DFS recursion.