Path Sum II LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft
Service Now Walmart Global techViews 3236

Problem Statement :

Path Sum II LeetCode Solution – 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.

Path Sum II LeetCode Solution

 

Approach :

Idea :

So what we have here…
We are given a root of a Binary Tree and we have to find a root-to-leaf path sum equal to targetSum (given). So, to solve this we have to go deep down into trees .. so.. DFS comes into light.  The simplest Easy approach we’ll follow.

Explanation :

so the plan is :

We will traverse each possible node and subtract the mode value from targetSum. If we reach the leaf node then we will check if it turns zero or not.

1. We will be required an array “path” to store the current path and another array “res” to store the final answer to the problem.
2. We start our traversing from the root. Decrement the value of targetSum and also add the value to the “path” array as we have to return the root-to-leaf path.
3 . Then we will go deeper; using  both the child: left and right and subtract that node value from targetSum  and also appending in path array until we reach any leaf nodes(Node has no child)

4. When we reach any leaf node, we have to subtract the current node value from targetSum and check if targetSum turns zero or not.
if it is, store the path (array) to res array. if not.. do nothing.

And the traversal goes on.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(root,targetSum,path):
            if not root :
                return 
            if root.left is None and root.right is None and targetSum - root.val == 0 :
                res.append(path + [root.val])
            dfs(root.left,targetSum - root.val , path + [root.val])
            dfs(root.right,targetSum - root.val , path + [root.val])
        dfs(root,targetSum,[])
        return res

 

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null)
            return res;
        dfs(root, targetSum, new ArrayList<>());
        return res;
    }

    void dfs(TreeNode node, int targetSum, ArrayList<Integer> path) {
        if(node == null)
            return;
            path.add(node.val);
            targetSum -= node.val;
        
        if(targetSum == 0 && node.left == null && node.right == null)
            res.add(path);
        
        dfs(node.left, targetSum, new ArrayList<>(path));
        dfs(node.right, targetSum, new ArrayList<>(path));
    }
}

Complexity Analysis for Path Sum II LeetCode Solution:

As we have visited each node, so Time Complexity will be O(n)

and we are storing the path. so that cost extra space of O(n) as well.

That’s it. code is done.

N.B: in the python solution, I have used Nested Function.

Translate »