113. Path Sum II

MediumTreeDepth-First SearchBacktrackingBinary Tree

Problem Description

In this problem, we are given a binary tree and an integer targetSum. Our task is to find all the different paths from the root of the binary tree to any of its leaves such that the sum of node values along each path is equal to targetSum. A root-to-leaf path is defined as a path that begins at the root node and ends at a leaf node, where a leaf node is a node that does not have any children. The solution should return all such paths as lists of node values.

Flowchart Walkthrough

Let's analyze Leetcode 113: Path Sum II using the Flowchart. We will step through the flowchart to determine the correct algorithm to use.

Is it a graph?

Yes: Although this problem is about a tree, in computer science, trees are a type of graph with nodes and edges where each child node has only one parent.

Is it a tree?

Yes: The problem explicitly involves a binary tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although trees are DAGs by definition, the typical usage of DAGs in problems refers to more complex scenarios like scheduling tasks. This problem is strictly about finding paths in a tree.

Is the problem related to shortest paths?

No: The task requires finding all root-to-leaf paths where each path's sum equals a given target, not about finding the shortest path in terms of distance or cost.

Does the problem involve connectivity?

No: Connecting nodes differently is not the goal; the tree's structure is fixed, and we are interested in specific paths from root to leaves that meet a criteria (specific sum).

By following the decision gates provided by the flowchart and considering the specifics of the problem, we arrive at utilizing a Depth-First Search (DFS) strategy. DFS is appropriate here because we need to explore entire paths from the root to each leaf to check whether they sum to the target value. This approach allows for backtracking after exploring each path, which is ideal for this problem's requirements.

Intuition

The intuition behind the solution is to traverse the tree in a depth-first search (DFS) manner. We can start from the root and recursively visit each node's children until we reach the leaf nodes. As we traverse the tree, we can keep track of the sum of the values of the nodes along the path and the nodes themselves in a list.

When we reach a leaf node (a node with no children), we check if the sum of the path is equal to targetSum. If it is, we found a valid path and add a copy of the current path list to an answer array that we maintain to store all valid paths. If the sum is not equal to targetSum, we simply backtrack and continue exploring other nodes and paths.

The key aspects of the solution are:

Starting from the root, perform DFS to explore all paths to leaf nodes.
Keep a running sum of node values for the current path being explored.
Keep a temporary list to track the node values for the current path.
If a leaf node is reached where the running sum is equal to targetSum, add the current path to the solution list.
After processing a node, backtrack by popping the last node value from the temporary path list before returning to the parent node.

This approach allows us to systematically explore all potential paths in the tree and collect the ones that satisfy the condition without missing any.

Learn more about Tree, Depth-First Search, Backtracking and Binary Tree patterns.

Solution Approach

The solution uses a recursive depth-first search (DFS) strategy to explore all possible root-to-leaf paths in the binary tree.

Let's walk through the key components of the implementation:

The dfs function is a helper function that we define within the pathSum method. It takes two arguments:
- The root of the current subtree that we are exploring.
- A running sum s that starts at 0 and accumulates the sum of node values from the root to the current node.
A list t is used to maintain the current path, representing the sequence of node values from the root to the current node being visited.
A list ans is maintained to store all successful paths that sum up to targetSum.

The dfs function works as follows:

If the current node root is None, we have hit a dead-end and need to terminate this branch of recursion.
We add the current node's value to the running sum s and append this value to t to track the path.
If the current node is a leaf (neither left nor right child exists), and the running sum s equals targetSum, we have found a successful path. We make a shallow copy of t using t[:] and append this copy to ans to record the successful path.
We recursively call dfs on the left and right children of the current node, with the updated running sum s.
After exploring both children, we backtrack by popping the last element from t, ensuring that t reflects the path for its predecessors as we return to the parent node.

By calling dfs(root, 0) initially, we begin the search from the root of the entire tree with an initial sum of 0. We keep exploring recursively as described above until all possible paths have been checked for the condition.

The return value of the pathSum function is ans, which contains lists of node values for all the root-to-leaf paths that add up to targetSum.

This approach effectively employs DFS traversal and backtracking to explore the tree's paths and return only those that meet the given criteria.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a binary tree and a targetSum of 22 for our example:

     5
    / \
   4   8
  /   / \
 11  13  4
/  \      \
7    2      5

We want to find all root-to-leaf paths where the sum of the node values is equal to targetSum.

We'll use the DFS approach to navigate through this tree and look for such paths. Using the solution approach described earlier, we will track both the current sum of the path and the path of node values itself as we progress. Here's how it would work, step-by-step:

We start with the root node (5), add it to our path and running sum s is now 5.
We move to the left child (4), include it in our path. So, our path is now [5, 4] and s becomes 9.
Continuing deeper, we reach node 11 and our path is [5, 4, 11], with s updating to 20.
We move to node 7, and now the path becomes [5, 4, 11, 7] and s is 27. Since this is a leaf, we check if s is equal to targetSum (22). It is not, so we backtrack to 11.
We then visit the right child of 11, which is node 2, making the path [5, 4, 11, 2] and s is now 22. This is a leaf node and the sum matches targetSum, so this path is added to our answer list.
After checking both children of node 11, we backtrack to node 4 and then to node 5, and proceed to its right child (8). Our path is now [5, 8] and s becomes 13.
Node 8 has two children, so we explore the left child first (node 13). Although now s becomes 26, since 13 has no children, we quickly backtrack to 8 without changing our path list.
Moving to the right child of node 8 (node 4), the path and sum update to [5, 8, 4] and s of 17, respectively.
Node 4 has one child, which is a leaf (node 5). We visit it, and the path becomes [5, 8, 4, 5] and s sums up to 22, which is equal to targetSum. We add this path to the list of valid paths.
All nodes are visited, and we've now found all the required paths. We populate these into our answers list.

The result of the search using our example tree and targetSum is the following list of paths:

[
  [5, 4, 11, 2],
  [5, 8, 4, 5]
]

The DFS approach has successfully identified all the paths whose node values sum up to the targetSum.

Solution Implementation

1# Here we define a TreeNode class for the binary tree nodes.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.current_left = left
6        self.current_right = right
7
8class Solution:
9    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
10        # Helper method to perform depth-first search.
11        def dfs(node, current_sum):
12            nonlocal targetSum, paths, current_path
13            if node is None:
14                return
15
16            # Add the current node's value to the running sum.
17            current_sum += node.val
18            # Add the current node's value to the current path being evaluated.
19            current_path.append(node.val)
20
21            # Check if we're at a leaf node and the running sum equals the target sum.
22            if node.current_left is None and node.current_right is None and current_sum == targetSum:
23                # If so, add a copy of the current path to the list of paths.
24                paths.append(current_path[:])
25
26            # Continue the search on the left and right subtrees.
27            dfs(node.current_left, current_sum)
28            dfs(node.current_right, current_sum)
29          
30            # We've finished exploring from this node, so backtrack and remove the node value from the current path.
31            current_path.pop()
32
33        # This will hold all the paths that sum to the target.
34        paths = []
35        # Temp list to hold the current path being checked.
36        current_path = []
37        # Initialize the DFS from the root node with a sum of 0.
38        dfs(root, 0)
39        return paths
40

1/**
2 * Definition for a binary tree node.
3 * This class defines the structure of the tree node which includes
4 * a value, and references to the left and right child nodes.
5 */
6class TreeNode {
7    int val;
8    TreeNode left;
9    TreeNode right;
10
11    TreeNode() {}
12  
13    TreeNode(int val) { 
14        this.val = val; 
15    }
16  
17    TreeNode(int val, TreeNode left, TreeNode right) {
18        this.val = val;
19        this.left = left;
20        this.right = right;
21    }
22}
23
24/**
25 * Solution class where we define the method to find all root-to-leaf paths
26 * that add up to a given target sum.
27 */
28class Solution {
29    // A list to store all the paths that sum to the target
30    private List<List<Integer>> paths = new ArrayList<>();
31    // A temporary list to keep track of the current path
32    private List<Integer> currentPath = new ArrayList<>();
33
34    /**
35     * Finds all paths from root to leaves that sum to targetSum.
36     * @param root The root of the tree.
37     * @param targetSum The sum that each path needs to add up to.
38     * @return A list of all paths that sum to targetSum.
39     */
40    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
41        dfs(root, targetSum);
42        return paths;
43    }
44
45    /**
46     * Performs a depth-first search to find all paths with the target sum.
47     * @param node The current node in the recursion.
48     * @param remainingSum The remaining sum after subtracting the node's value.
49     */
50    private void dfs(TreeNode node, int remainingSum) {
51        if (node == null) {
52            // If we've reached a null node, just return.
53            return;
54        }
55      
56        // Subtract the node's value from the remaining sum and add the node's value to the current path
57        remainingSum -= node.val;
58        currentPath.add(node.val);
59      
60        // Check if it's a leaf node and the remaining sum is zero, which means we've found a valid path
61        if (node.left == null && node.right == null && remainingSum == 0) {
62            // If so, add a copy of the current path to the list of valid paths
63            paths.add(new ArrayList<>(currentPath));
64        }
65
66        // Recurse deeper into the tree
67        dfs(node.left, remainingSum);  // Go left
68        dfs(node.right, remainingSum); // Go right
69      
70        // After exploring both sides, remove the current node's value before going back up the tree
71        currentPath.remove(currentPath.size() - 1);
72    }
73}
74

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Main function to find all paths that sum to the target.
16    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
17        vector<vector<int>> allPaths; // Stores all paths that sum to targetSum.
18        vector<int> currentPath; // Holds the current path being evaluated.
19
20        // Helper function to perform DFS on the tree
21        function<void(TreeNode*, int)> depthFirstSearch = [&](TreeNode* node, int remainingSum) {
22            if (!node) // Base case: If the node is null, return.
23                return;
24          
25            remainingSum -= node->val; // Subtract the node's value from the remaining sum.
26            currentPath.emplace_back(node->val); // Add the current node's value to the path.
27
28            // Check if it's a leaf node and the remaining sum is 0; if so, store the path.
29            if (!node->left && !node->right && remainingSum == 0) {
30                allPaths.emplace_back(currentPath);
31            }
32
33            // Continue searching in the left and right subtrees.
34            depthFirstSearch(node->left, remainingSum);
35            depthFirstSearch(node->right, remainingSum);
36
37            // Backtrack: remove the last element before returning to the previous caller.
38            currentPath.pop_back();
39        };
40
41        // Start the depth-first search with the original root and target sum.
42        depthFirstSearch(root, targetSum);
43
44        // Return all found paths after the search is complete.
45        return allPaths;
46    }
47};
48

1// Definition for a binary tree node
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14/**
15 * Main function to find all paths that sum to the target value
16 * @param root The root of the binary tree
17 * @param targetSum The sum to find in the binary tree
18 * @return An array of arrays, where each array represents a path that sums to targetSum
19 */
20const pathSum = (root: TreeNode | null, targetSum: number): number[][] => {
21    const allPaths: number[][] = []; // To store all the valid paths.
22    const currentPath: number[] = []; // To keep track of the current path.
23
24    // Helper function to perform DFS (Depth First Search) on the binary tree
25    const dfs = (node: TreeNode | null, remainingSum: number) => {
26        if (!node) return; // Base case: if the current node is null, do nothing.
27
28        remainingSum -= node.val; // Subtract the current node value from the remaining sum.
29        currentPath.push(node.val); // Insert the current node value into the current path.
30
31        // Check if it's a leaf node and the remaining sum is 0, which means we've found a valid path.
32        if (!node.left && !node.right && remainingSum === 0) {
33            allPaths.push([...currentPath]); // Add a copy of the current path to allPaths.
34        }
35
36        dfs(node.left, remainingSum); // Continue DFS on the left subtree.
37        dfs(node.right, remainingSum); // Continue DFS on the right subtree.
38
39        currentPath.pop(); // Backtrack: remove the last node value from the current path.
40    };
41
42    dfs(root, targetSum); // Start DFS with the root node and the initial targetSum.
43
44    return allPaths; // Return all the valid paths.
45};
46
47export { TreeNode, pathSum }; // Exporting the TreeNode class and pathSum function for other modules to use.
48

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the tree. This is because in the worst case, the algorithm will visit each node exactly once while performing depth-first search (DFS).

Space Complexity

The space complexity is more complex to analyze due to the space taken by the recursion stack and the space required to store the paths.

Recursion Stack: The space taken by the recursion stack is proportional to the height of the tree. In the worst case for a skewed tree, the height can be n leading to O(n) complexity. In the best case for a balanced tree, the height will be log(n), leading to O(log(n)) complexity.
Path Storage: For every leaf node, we potentially have a path equal in size to the tree's height. In the worst case (all paths are saved), this results in O(n * h) space, where h is the height of the tree. However, since the height can range from log(n) for a balanced tree to n for a skewed tree, the space complexity for storing paths ranges from O(n * log(n)) to O(n^2).

Considering these aspects, the total space complexity of the code can be O(n * h) where h is the height of the tree. The exact bound depends on the shape of the tree. In the case of a balanced tree, the space complexity would be O(n * log(n)), while for a completely unbalanced tree, it would be closer to O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know