Riyaz

Posted on

# Path Sum(code and Explanation)

Problem Statement
Q.)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.
Binary tree
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 = 22

Intuition
Lets say you know this question requires you to use DFS but how are you going to store the individual values of all the node and sum them to find if they are equal to targetSum.
For a complete beginner it may not come handy unless you have practiced a lot of such questions.
Now in the iterative version of DFS you know that you have to use stack to remember visited nodes and traverse further.So you are aware that stack is used to store the nodes.So instead of storing only the nodes in the stack you can also store a tuple inside the stack along with the node’s sum of all the previous node value.Something like this
stack
This little trick is hard to come up with your own,but once you know it you can solve many questions regarding the DFS of Binary Tree i.e now you know that you can use the stack itself to store more data about the binary tree.
SOLUTION:

``````def pathSum(root):
if not root: return None
stack = [(root,root.val,[root.val])]
ans = []
while stack:
node,val,li = stack.pop()
if not node.left and not node.right and val == targetSum:
ans.append(li)
if node.right:
stack.append((node.right,val+node.right.val,li+[node.right.val]))
if node.left:
stack.append((node.left,val+node.left.val,li+[node.left.val]))

return ans
``````

This trick of storing using tuples in stack will help you solve a lot more questions