# Tree: find all paths for a target sum DFS recursive with helper Python

Tue Jul 19 2022 00:13:34 GMT+0000 (Coordinated Universal Time)

```class Tree(object):
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right

tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))

def find_paths(root, required_sum):
allPaths = []

def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
if currentNode is None:
return

# add the current node to the path
currentPath.append(currentNode.val)

# if the current node is a leaf and its value is equal to required_sum, save the current path
if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
allPaths.append(list(currentPath))
else:
# traverse the left sub-tree
find_paths_recursive(currentNode.left, required_sum -
currentNode.val, currentPath, allPaths)
# traverse the right sub-tree
find_paths_recursive(currentNode.right, required_sum -
currentNode.val, currentPath, allPaths)

# remove the current node from the path to backtrack,
# we need to remove the current node while we are going up the recursive call stack.
del currentPath[-1]

find_paths_recursive(root, required_sum, [], allPaths)

return allPaths

find_paths(tx, 5)```
content_copyCOPY

Good to plug this into python tutor. The deletion of current Path was interesting.