In a class for tree-structured data, I'm trying to get the path from a certain node to the root.
The get_forward_path() method below works in the first run, but its output list grows forever everytime I run the method. It keeps growing even if I apply the method to different nodes.
Why does it happen even though the path argument is reset to its default (the blank list) when the method is called?
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
self.parent = None
def add_child(self, child):
child.parent = self
self.children.append(child)
def print_tree(self):
spaces = ' ' * self.get_level() * 3
prefix = spaces + "|__" if self.parent else ""
print(prefix + self.data)
if self.children:
for child in self.children:
child.print_tree()
def get_forward_path(self,path=[]):
if not self.parent:
path.append(self.data)
else:
path.append(self.data)
p = self.parent
p.get_forward_path(path)
return path[::-1]
def get_level(self):
level = 0
p = self.parent
while p:
level += 1
p = p.parent
return level
root = TreeNode("Electronics")
laptop = TreeNode("Laptop")
Mac = TreeNode("Mac")
Surface = TreeNode("Surface")
ThinkPad = TreeNode("ThinkPad")
laptop.add_child(Mac)
laptop.add_child(Surface)
laptop.add_child(ThinkPad)
cellphone = TreeNode("Cell Phone")
iPhone = TreeNode("iPhone")
Google_Pixel = TreeNode("Google Pixel")
Vivo = TreeNode("Vivo")
cellphone.add_child(iPhone)
cellphone.add_child(Google_Pixel)
cellphone.add_child(Vivo)
tv = TreeNode("TV")
Samsung = TreeNode("Samsung")
LG = TreeNode("LG")
tv.add_child(Samsung)
tv.add_child(LG)
root.add_child(laptop)
root.add_child(cellphone)
root.add_child(tv)
root.print_tree()
Electronics
|__Laptop
|__Mac
|__Surface
|__ThinkPad
|__Cell Phone
|__iPhone
|__Google Pixel
|__Vivo
|__TV
|__Samsung
|__LG
Samsung.get_forward_path()
['Electronics', 'TV', 'Samsung']
Samsung.get_forward_path()
['Electronics', 'TV', 'Samsung', 'Electronics', 'TV', 'Samsung']
iPhone.get_forward_path()
['Electronics',
'Cell Phone',
'iPhone',
'Electronics',
'TV',
'Samsung',
'Electronics',
'TV',
'Samsung']
Recursion is a functional heritage and so using it with functional style yields the best results. That means avoiding things like mutation, variable reassignment, and other side effects.
When you write path.append(something), the append function mutates the path variable. Instead of mutating, use + which concatenates lists in a nondestructive way -
def get_forward_path(self, path=[]):
next_path = [self.data] + path # ✅ no mutation!
if not self.parent:
return next_path
else:
return self.parent.get_forward_path(next_path)
Adhering to this discipline, there is no issue using path=[] with default value.
Added benefit, notice we prepend the data as the output list is created, which means we don't have to think about reversing the final output.