Schematic: Having a node class meant to support tree structures. Every instance of this class will have a dictionary for all their children, a a parent, and the data to be stored.
make_children takes the calling object and adds the argument as a child. The childs parent is set to self as the current calling object is the parent node. This child is then added to the current objects dictionary as a child.
print_tree takes the current calling object and prints the value attribute while calling itself recursively and stopping once hitting a leaf node.
I am attempting to play around with and learn about recursion and trees. I am trying to get the following output.
[12, 7, 8, 15]
[12, 7]
[8, 15]
[12]
[7]
[8]
[15]
Instead get:
[12, 7, 8, 15]
[12, 7]
[8, 15]
What am I be doing wrong? I suspect the issue lies with with print_tree, the recusion in build_file_tree, or the return statement in build_file_tree. I tried printing left and right half using print statements and they seem to work correctly, which makes me lean more towards print_tree.
class Node:
def __init__(self, value):
self.value = value
self.children = []
self.parent = None
def make_children(self, child):
child.parent = self
self.children.append(child)
def print_tree(self): #ISSUE?
print(self.value)
if len(self.children) > 0: # leaf node case
for child in self.children:
child.print_tree()
def build_file_tree(list1):
#list1 = [12, 7, 8, 15]
#root = Node(56)
root = Node(list1)
#child1 = Node(12)
#child2 = Node(24)
temp = len(list1) // 2
left_half = list1[:temp]
right_half = list1[temp:]
if len(left_half) > 1: # ISSUE HERE?
build_file_tree(left_half)
if len(right_half) > 1: # ISSUE HERE?
build_file_tree(right_half)
child1 = Node(left_half)
child2 = Node(right_half)
root.make_children(child1)
root.make_children(child2)
return root #ISSUE?
if __name__ == '__main__':
list1 = [12, 7, 8, 15]
file = build_file_tree(list1)
file.print_tree()
>Solution :
This was a hard one.
Steps to debug:
def __init__(self, value):
print(f"Creating node for {value}")
This will show you that you actually create two different trees. This is due to calling Node (which should be called Tree) on left_half as Node(left_half) and then in build_file_tree(left_half) as Node(list1).
This means that every subtree will only have a height of 2 levels after which you’ll call make_children with a fresh instance that does not have their parent relation set.
My Solution would be to change the build_file_tree function as follows:
def build_tree(value_list):
root = Tree(value_list)
if len(value_list) == 1:
return root
mid_point = len(value_list) // 2
left_half = value_list[:mid_point]
right_half = value_list[mid_point:]
child1 = build_tree(left_half)
root.make_child(child1)
child2 = build_tree(right_half)
root.make_child(child2)
return root
I did some light refactoring but you should be able to get the idea