113. Path Sum II
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 thepathSum
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.
- The
-
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 totargetSum
.
The dfs
function works as follows:
-
If the current node
root
isNone
, 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 tot
to track the path. -
If the current node is a leaf (neither
left
norright
child exists), and the running sums
equalstargetSum
, we have found a successful path. We make a shallow copy oft
usingt[:]
and append this copy toans
to record the successful path. -
We recursively call
dfs
on theleft
andright
children of the current node, with the updated running sums
. -
After exploring both children, we backtrack by popping the last element from
t
, ensuring thatt
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 EvaluatorExample 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]
ands
becomes 9. - Continuing deeper, we reach node 11 and our path is
[5, 4, 11]
, withs
updating to 20. - We move to node 7, and now the path becomes
[5, 4, 11, 7]
ands
is 27. Since this is a leaf, we check ifs
is equal totargetSum
(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]
ands
is now 22. This is a leaf node and the sum matchestargetSum
, 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]
ands
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]
ands
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]
ands
sums up to 22, which is equal totargetSum
. 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 toO(n)
complexity. In the best case for a balanced tree, the height will belog(n)
, leading toO(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, whereh
is the height of the tree. However, since the height can range fromlog(n)
for a balanced tree ton
for a skewed tree, the space complexity for storing paths ranges fromO(n * log(n))
toO(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.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Want a Structured Path to Master System Design Too? Donāt Miss This!