I'm trying to write an algorithm in python to print out all paths from the root of a (binary) tree to each leaf. Here's my code:
def fb_problem(node, curr_trav):
curr_trav = curr_trav + [node]
if node.left is None and node.right is None:
for path_node in curr_trav:
print path_node.data
print "XXX"
if node.left is not None:
fb_problem(node.left, curr_trav)
if node.right is not None:
fb_problem(node.right, curr_trav)
fb_problem(root, [])
I keep a list of nodes in the current traversal, and when I've reached a leaf, I print out the list. I'm misunderstanding something about the way python passes objects though. I thought that as each recursive call completes and is popped off the stack, the original curr_trav variable would not be affected by what the recursive call did. However, it seems as if the line
curr_trav += [node]
Is mutating the original list. The += operator returns a new list, as opposed to .append(), which actually mutates the original object. So shouldn't this call just be reassigning the name given to the object in the function, not mutating the original object? When I change the line to something like
t_trav = curr_trav += [node]
Everything works fine, but I don't understand what the problem with the original line was. Please let me know if my question is unclear.
Your understanding of += is not quite correct. All operators in Python are really just shortcuts. For example, a + b is a.__add__(b) if a has an __add__ method. If a does not, it is b.__radd__(a). If b doesn't have that method, an error is raised. Usually, a += b behaves quite like a = a + b, but in the case of mutable objects, it usually doesn't. That is because a += b is a.__iadd__(b) if a has the __iadd__ method. If a does not, it is the same as a = a.__add__(b). If a doesn't have that either, it is the same as a = b.__radd__(a). Since lists do have the __iadd__ method, the actual list object is changed instead of redefining curr_trav.