Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’

Question

The example below is from a source online and what I'm not sure of is why we need to append to allPaths a new copy of currentPath. I thought that in deleting the last element as we go back up the recursive call stack by doing del currentPath[-1] makes sure that we are not adding the previous path to the new path

class TreeNode:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return 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]


def main():

  root = TreeNode(12)
  root.left = TreeNode(7)
  root.right = TreeNode(1)
  root.left.left = TreeNode(4)
  root.right.left = TreeNode(10)
  root.right.right = TreeNode(5)
  required_sum = 23
  print("Tree paths with required_sum " + str(required_sum) +
        ": " + str(find_paths(root, required_sum)))


main()

Answer 1

It is important to realise that during the whole process there is only one currentPath list. It is the one that is created in the initial call:

find_paths_recursive(root, required_sum, [], allPaths)
#                                        ^^---here!

All that happens to that single list is that elements are appended to it, and then deleted from it again (when backtracking). It continually grows and shrinks, grows and shrinks,... throughout its lifetime. But it is the same, single list instance.

If you were to append that list to allPaths without taking a copy, i.e. like this:

allPaths.append(currentPath)

...then realise that while that list is a member of allPaths, it will be mutated by future append and delete actions on it! Even more: as the above statement is executed again later on:

allPaths.append(currentPath)

... exactly the same list is appended that is already in allPaths... because there is only one currentPath list! So you'll end up with allPaths having repeated references to one and the same list.

Concluding: it is important to take a copy of currentPath which will not be mutated any more by the future mutations on currentPath. It is like taking a snapshot of the current state of currentPath.