Creating a binary tree

Question

I'm trying to create a tree from a flat list. I need to define a function called tree_from_flat_list. For any node at index position i, the left child is stored at index position 2*i, and the right child is stored at index position 2*i+1. :

class BinaryTree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def set_left(self, tree):
        self.left = tree

    def set_right(self, tree):
        self.right = tree

    def set_data(self, data):
        self.data = data

    def get_data(self):
        return self.data

    def create_string(self, spaces): 
        info = ' ' * spaces + str(self.data) 
        if self.left != None: 
            info += '\n(l)' + self.left.create_string(spaces+4) 
        if not self.right == None: 
            info += '\n(r)' + self.right.create_string(spaces+4) 
        return info       

    def __str__(self): 
        representation = self.create_string(0) 
        return representation 

def tree_from_flat_list(node_list):
    if node_list != None:
        root_index = 1
        list1 = []
        list2 = []
        root = node_list[root_index]
        left_sub_tree = list1.append(node_list[2*root_index])
        right_sub_tree = list2.append(node_list[2*root_index+1])
        tree = BinaryTree(root)
        tree.set_left(tree_from_flat_list(left_sub_tree))
        tree.set_right(tree_from_flat_list(right_sub_tree))
        return tree

When I try running this:

def test():
    flat_list = [None, 10, 5, 15, None, None, 11, 22]
    my_tree = tree_from_flat_list(flat_list)
    print(my_tree)

test()

I should get the output:

10
(l)    5
(r)    15
(l)        11
(r)        22

Edit: Still stuck on what I should be doing for the function. Any help is still appreciated.

the amount of spaces inbetween is the height of the tree and the l and r represent if they are a left child or a right child. This would looks like:

but instead I only get:

How should I edit my tree_from_flat_list function so that this works. Any help is appreciated. Thank you.

Can you add some information (in textual format) about how a tree is supposed to be constructed from the list? — L3viathan
– L3viathan, Commented Feb 13, 2017 at 11:16
Can you explain what exactly your printed output is suppose to represent? What exactly is the structure of the binary tree that should be made from [None, 10, 5, 15, None, None, 11, 22]? I could start making assumptions, but it would be better if you just specified this from the start. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 13, 2017 at 11:20
Also, don't use getters and setters, this is Python, not Java. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 13, 2017 at 11:20
So, according to your specification, the list will always start with None? — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 13, 2017 at 11:22
@EllenPage Then where will the node for the left child go for the node at index 0? — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 13, 2017 at 11:35

doctorlove · Accepted Answer · 2017-02-13 11:36:48Z

3

The essence of your problem is in these lines:

    left_sub_tree = list1.append(node_list[2*root_index])
    right_sub_tree = list2.append(node_list[2*root_index+1])

The append function sets doesn't return anything - it appends to the list. This sets your left and right sub trees to None.

edited Feb 13, 2017 at 11:36

answered Feb 13, 2017 at 11:28

doctorlove

19.4k3 gold badges49 silver badges65 bronze badges

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

3 Comments

Ellen Page Over a year ago

This was indeed the essence of my problem. Thank you for pointing it out for me.

Ellen Page Over a year ago

I'm still stuck on this part. How would I go around doing it so that I instead set my left and sub trees to the correct values.

doctorlove Over a year ago

@L3viathan's approach is much neater - try using that?

L3viathan · Accepted Answer · 2017-02-13 11:35:25Z

2

The list format seems to be a variant of a binary heap where elements can be None. I think you can simplify this quite a bit:

class BinaryTree(object):
    def __init__(self, label, left, right):
        self.label = label
        self.left = left
        self.right = right

def tree_from_flat_list(ls, index=1):
    if index < len(ls) and ls[index] is not None:
        left = tree_from_flat_list(ls, 2*index)
        right = tree_from_flat_list(ls, 2*index+1)
        return BinaryTree(ls[index], left, right)

I wonder though why you don't store the left and right children in indices 2*i+1 and 2*i+2, like in a binary heap; then you don't need to have the None at the beginning.

answered Feb 13, 2017 at 11:35

L3viathan

27.5k2 gold badges63 silver badges84 bronze badges

Collectives™ on Stack Overflow

Creating a binary tree

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related