Discrepancy of list append in python

Question

I am getting a different result when I am using append(path) vs. append(list(path))

I have the following code to find all paths for a sum:

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


def find_paths(root, sum):
  allPaths = []
  
  dfs(root, sum, [], allPaths)

  return allPaths

def dfs(root, sum, path, res):
  if not root:
    return
  
  path.append(root.val)
  if root.val == sum and root.left is None and root.left is None:
    res.append(path)
  
  dfs(root.left, sum - root.val, path, res)
  dfs(root.right, sum - root.val, path, res)

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


main()

This has the following output:

Tree paths with sum 23: [[], []]

But if I change the res.append(path) to res.append(list(path)) which will then return the correct answer Tree paths with sum 23: [[12, 7, 4], [12, 1, 10]]. I am confused on why using the list operation would change the answer.

.append() doesn't make a copy of the element being appended. When you do del path[-1], you affect the list that was appended to res in exactly the same way that you affect path, because they're the same object. list(path) makes a copy (path.copy() would be a more usual way of writing that), so it's effectively a snapshot of the contents at that moment in time. — jasonharper
– jasonharper, Commented Apr 28, 2022 at 3:44

j1-lee · Accepted Answer · 2022-04-28 03:49:01Z

2

res.append(path) appends the object path itself to the list res. After that line, when you modify the path object (like del path[-1]), the modification is also applied to the appended object in res, because, well, they are the same object.

list(path), on the other hand, "copies" the path. So this one is now a different object from path. When you modify path after that, the modification does not propagates to this different object.

You will have the same result if you do path[:] or path.copy() instead of list(path).

edited Apr 28, 2022 at 3:49

answered Apr 28, 2022 at 3:43

j1-lee

13.9k3 gold badges16 silver badges27 bronze badges

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

Comments

John Gordon · Accepted Answer · 2022-04-28 03:44:13Z

1

res.append(path) appends the actual path object, not a copy of it. So if path changes later on, the change will appear in res also.

res.append(list(path)) appends a copy.

answered Apr 28, 2022 at 3:44

John Gordon

33.8k9 gold badges48 silver badges72 bronze badges

Collectives™ on Stack Overflow

Discrepancy of list append in python

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related