python understanding lists in recursion

Question

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: [[], []]

Please add an example, best if it is an example that fails, that it does not works without the list. Probably it is because list(path) creates a copy of the list. — Dani Mesejo
– Dani Mesejo, Commented Oct 9, 2019 at 2:20
I just change the list(path) to path[:] just another way of creating a copy and it works, so it is related to copying a list, when you do paths.append(path) you are appending the reference to path, so basically if you modify it in any other call, it becames empty. — Dani Mesejo
– Dani Mesejo, Commented Oct 9, 2019 at 2:27
nice so every time it gets passed to the stack it's adding a reference because it's being called from another function. thank you! — edmamerto
– edmamerto, Commented Oct 9, 2019 at 2:29

Dani Mesejo · Accepted Answer · 2019-10-09 02:29:59Z

1

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.

answered Oct 9, 2019 at 2:29

Dani Mesejo

62.2k6 gold badges56 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

python understanding lists in recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related