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

PHOTO EMBED

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

Saved by @bryantirawan #python #tree #recursion #dfs #neetcode

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.