Non-binary tree recursion

Question

I am trying to make a program that sets up a non-binary tree with each node being connected to children. In this test example, I used a binary tree for simplicity. The input is this:

1
3   5
4   6

(Tab characters are used between numbers). I am trying to generate the tree starting at the root (1), with its children being 3 and 5, and each of those nodes have children 4 and 6. The tree diagram might look something like this:

When I try to add children to my tree, it creates an infinite loop calling my recursion function. I've narrowed down the problem to it calling the function with branch being 1 on loop, but here is the code:

# input is a list of branch values
file = open("treehash.txt","r")
input = file.readlines()
for line in range(len(input)):
input[line] = input[line].rstrip().split('\t')
file.close()

# create the tree node
class Tree(object):
    value = None
    children = []
    def __init__(self, value):
        self.value = value

# adds all children to a given parent
def set_children(parent, branch):
    if branch < len(input) - 1:
        for num in input[branch + 1]:
            parent.children.append(Tree(int(num)))
        for child in parent.children:
            set_children(child, branch + 1)

# store all roots in array
roots = []
for root in range(len(input[0])):
    roots.append(Tree(int(input[0][root])))
    set_children(roots[root], 0)

If 4 and 6 have more than one parent, you have a graph, not a tree. — Blckknght
– Blckknght, Commented Dec 19, 2017 at 22:50
The 4 and 6 are unique to 3 and 5. There are two occurrences of each in the example. However, I suppose I have a graph if I start with multiple roots. — adapap
– adapap, Commented Dec 19, 2017 at 23:47

Michael Butscher · Accepted Answer · 2017-12-19 22:08:10Z

1

If you write variables in a class like you did with

class Tree(object):
    value = None
    children = []

they are bound to the class, not an instance. For value you overwrite it with an instance-bound variable in the __init__ constructor but the list referred by children is shared by all Tree instances.

Delete above variable settings and use instead:

class Tree(object):
    def __init__(self, value):
        self.value = value
        self.children = []

answered Dec 19, 2017 at 22:08

Michael Butscher

11k4 gold badges28 silver badges28 bronze badges

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

Collectives™ on Stack Overflow

Non-binary tree recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related