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:

 10
 / \
 5 15
 / \
 11 22

but instead I only get:

10

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

• L3viathan: Can you add some information (in textual format) about how a tree is supposed to be constructed from the list?
• juanpa.arrivillaga: 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: Also, don't use getters and setters, this is Python, not Java.
• juanpa.arrivillaga: So, according to your specification, the list will always start with None?
• juanpa.arrivillaga: @EllenPage Then where will the node for the left child go for the node at index 0?

Answer 1

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.

• Ellen Page: This was indeed the essence of my problem. Thank you for pointing it out for me.
• Ellen Page: 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: @L3viathan's approach is much neater - try using that?

Answer 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.