CODEWITHSUNDEEP
python
edmamerto
edmamerto

Reputation: 8165

python understanding lists in recursion

I have a recursive function that traverses a tree and gathers a list. I don't understand why I have to convert the "list" to a list. I added a comment in the code. removing list() would result to an empty list.

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

def find_paths(r, sum):

  def helper(root, summ, path, paths):
    if not root:
      return

    path.append(root.val)

    if not root.left and not root.right and summ == root.val:
      """
      if I print path

      [12, 7, 4]
      [12, 1, 10]
      """
      # why is list() necessary here
      paths.append(list(path))

    else:
      helper(root.left, summ - root.val, path, paths)  
      helper(root.right, summ - root.val, path, paths)

    del path[-1]

  paths = []
  helper(r, sum, [], paths)
  return paths

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)
  sum = 23
  print("Tree paths with sum " + str(sum) +
        ": " + str(find_paths(root, sum)))


main()

doing it just this way paths.append(path) will result to this Tree paths with sum 23: [[], []]

Upvotes: 0

Views: 48

Answers (1)

Dani Mesejo
Dani Mesejo

Reputation: 61920

The method list(path) creates a copy of the list, when you do:

paths.append(list(path))

You are actually appending a copy of the list, when you do:

paths.append(path)

You are appending the reference to the list so when you modify it like in:

del path[-1]

it affects the reference added to paths.

Upvotes: 1

Related Questions