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 ]

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

}

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) assuming recursive stack.