Error in recursively printing nodes of a tree-CodePudding

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()

CodePudding user response：

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

CodePudding user response：

You dont create a Child if the list has length 1. But you should do this, if you want the described behavior. Also you need to stop the recursion if list1 only contains one or less elements. And you didn't catch the returned root element. Your Code could look like this:

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)
    if len(list1) > 1:
        temp = len(list1) // 2
        left_half = list1[:temp]
        right_half = list1[temp:]

        child1 = build_file_tree(left_half)
        root.make_children(child1)

        child2 = build_file_tree(right_half)
        root.make_children(child2)

    return root


if __name__ == '__main__':
    list1 = [12, 7, 8, 15]
    file = build_file_tree(list1)
    file.print_tree()