Path Sum II
MedPrompt
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []Example 3:
Input: root = [1,2], targetSum = 0
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a standard Depth-First Search (DFS) traversal. The core idea is to explore each possible root-to-leaf path. For each node visited, we create a new list that represents the path from the root to the current node. This is done by copying the path of the parent node and appending the current node. This new path is then passed down to its children in subsequent recursive calls. While conceptually simple, this method is inefficient because of the repeated creation of list copies at every step of the recursion.
Algorithm
- Define a recursive helper function, for example,
findPaths(node, remainingSum, currentPath, result). - The base case for the recursion is when the
nodeisnull. In this case, simply return. - Inside the function, create a new list (
newPath) by copying thecurrentPathand add the current node's value to it. - Subtract the current node's value from
remainingSum. - Check if the current node is a leaf (both
leftandrightchildren arenull) and if theremainingSumis now zero. - If both conditions are true, it means we've found a valid path. Add the
newPathto the finalresultlist. - Recursively call the
findPathsfunction for the left and right children, passing the updatedremainingSumand thenewPath. - The main function will initialize an empty list for the results and call the helper function with the root node, the initial
targetSum, and an empty path.
Walkthrough
The algorithm explores the tree from the root downwards. It maintains the sum of the nodes along the path it is currently exploring. A helper function is used to carry the state of the traversal, which includes the current node, the sum still needed to reach the target (remainingSum), and the list of nodes in the current path.
At each node, we create a brand new list by copying the path that led to the parent and add the current node's value. We then update the remainingSum. If the current node is a leaf and the remainingSum is zero, we have found a valid path and add our new path list to the list of results. We then continue this process recursively for the left and right children.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> result = new ArrayList<>(); findPaths(root, targetSum, new ArrayList<>(), result); return result; } private void findPaths(TreeNode node, int remainingSum, List<Integer> currentPath, List<List<Integer>> result) { if (node == null) { return; } // Create a new path list for the path including the current node List<Integer> newPath = new ArrayList<>(currentPath); newPath.add(node.val); int newRemainingSum = remainingSum - node.val; // Check if it's a leaf node and the sum matches if (node.left == null && node.right == null && newRemainingSum == 0) { result.add(newPath); return; } // Recurse for left and right children, passing the new path findPaths(node.left, newRemainingSum, newPath, result); findPaths(node.right, newRemainingSum, newPath, result); }}Complexity
Time
O(N*H)
Space
O(N*H)
Trade-offs
Pros
The logic is straightforward and easy to understand.
The state for each recursive call (the path) is completely independent, which can prevent certain bugs related to shared state.
Cons
Highly inefficient in terms of both time and space.
Creating a new copy of the path list at every node in the tree leads to significant overhead, especially for deep or large trees.
This approach also uses Depth-First Search (DFS) but optimizes the process by using backtracking. Instead of creating a new path list for every recursive call, we use a single list to keep track of the current path. When we move down the tree to a child, we add its value to the list. After the recursive call for that child's subtree returns, we remove the value from the list. This action of removing the element is called 'backtracking'. It ensures that when we explore a sibling node, the path is correctly set to the state of the parent. This avoids the expensive operation of copying the path at every node, making it much more efficient in both time and space.
Algorithm
- Define a recursive helper function, e.g.,
findPaths(node, remainingSum)that uses shared lists for the result and the current path (e.g., as member variables). - The base case is when
nodeisnull; simply return. - Add the current node's value to the
currentPathlist. - Subtract the node's value from
remainingSum. - Check if the current node is a leaf (
node.left == null && node.right == null) and ifremainingSumis zero. - If so, a valid path is found. Add a copy of the
currentPathto theresultlist. It's crucial to add a copy, as thecurrentPathlist will be modified later during backtracking. - Recursively call the helper function for the left and right children with the updated
remainingSum. - After the recursive calls for the children return, remove the current node's value from the end of
currentPath. This is the backtracking step. It cleans up the path, effectively moving up one level in the tree, allowing other branches to be explored correctly.
Walkthrough
The algorithm traverses the tree using a recursive DFS function. We maintain a single list, path, which stores the nodes of the path currently being explored. When the DFS function is called on a node, we add that node's value to path. We then check if it's a leaf node and if the path sum equals the targetSum. If it does, we create a copy of the current path and add it to our list of results. We then proceed to make recursive calls for the left and right children. The crucial step happens after these recursive calls return: we remove the current node's value from path. This backtracking step ensures that the path list is restored to its state before visiting the current node, making it ready for the exploration of other branches of the tree.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { List<List<Integer>> result; List<Integer> path; public List<List<Integer>> pathSum(TreeNode root, int targetSum) { result = new ArrayList<>(); path = new ArrayList<>(); findPaths(root, targetSum); return result; } private void findPaths(TreeNode node, int remainingSum) { if (node == null) { return; } // Add current node to the path path.add(node.val); remainingSum -= node.val; // Check if it's a leaf and the sum is met if (node.left == null && node.right == null && remainingSum == 0) { result.add(new ArrayList<>(path)); } // Recurse on children findPaths(node.left, remainingSum); findPaths(node.right, remainingSum); // Backtrack: remove the current node from the path path.remove(path.size() - 1); }}Complexity
Time
O(N) for traversing all nodes. The total time is O(N + K*H) where K is the number of valid paths and H is the tree height, to account for copying valid paths to the result.
Space
O(H) or O(N) in the worst case (skewed tree), where H is the height of the tree. This is for the recursion stack and the path list, excluding the output.
Trade-offs
Pros
Very efficient in terms of time and space.
Avoids the overhead of creating new lists at each recursive step.
It's the standard and optimal solution for this type of path-finding problem in trees.
Cons
Backtracking can be slightly more complex to implement correctly compared to passing copies.
Requires careful state management of the shared path list to avoid bugs.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < List < Integer >> ans = new ArrayList <>(); private List < Integer > t = new ArrayList <>(); public List < List < Integer >> pathSum ( TreeNode root , int targetSum ) { dfs ( root , targetSum ); return ans ; } private void dfs ( TreeNode root , int s ) { if ( root == null ) { return ; } s -= root . val ; t . add ( root . val ); if ( root . left == null && root . right == null && s == 0 ) { ans . add ( new ArrayList <>( t )); } dfs ( root . left , s ); dfs ( root . right , s ); t . remove ( t . size () - 1 ); } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number[][]} */ var pathSum = function (root, targetSum) { const ans = []; const t = []; function dfs(root, s) { if (!root) return; s -= root.val; t.push(root.val); if (!root.left && !root.right && s == 0) ans.push([...t]); dfs(root.left, s); dfs(root.right, s); t.pop(); } dfs(root, targetSum); return ans; };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < vector < int >> pathSum ( TreeNode * root , int targetSum ) { vector < vector < int >> ans ; vector < int > t ; function < void ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int s ) { if ( ! root ) return ; s -= root -> val ; t . emplace_back ( root -> val ); if ( ! root -> left && ! root -> right && s == 0 ) ans . emplace_back ( t ); dfs ( root -> left , s ); dfs ( root -> right , s ); t . pop_back (); }; dfs ( root , targetSum ); return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def pathSum ( self , root : Optional [ TreeNode ], targetSum : int ) -> List [ List [ int ]]: def dfs ( root , s ): if root is None : return s += root . val t . append ( root . val ) if root . left is None and root . right is None and s == targetSum : ans . append ( t [:]) dfs ( root . left , s ) dfs ( root . right , s ) t . pop () ans = [] t = [] dfs ( root , 0 ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.