Create a binary tree from a given list

Question

I want to create a binary tree from a given list. How can I go about it? Suppose,

list = [0, 5400, 33735, 2317, 123, 242737, 0, 0, 0, 1368, 43654]

is the list I want to create a tree for.

I tried the following code but I am not sure what it is doing.

class Node:
 def __init__(self,data):
 self.left = None
 self.right = None
 self.data = data
def check():
nodelist = [Node(c) for c in list]
 i,y = 0,len(list)
 while True:
 for x in range(y):
 nodelist[i].left = nodelist[i-1] if x!=0 else None
 nodelist[i].right = nodelist[i+1] if x!=y-1 else None
 i+=1
 if i<len(list):
 y+=1
 else:
 break
 for n in nodelist:
 print unicode(n)

Pardon for my weakness in Algorithms. Data Structures really scare me off..

And generating a binary tree from given data in python is where I tried the code from.

• Burhan Khalid: "I tried the following code but I am not sure what it is doing" [a] this code, did you write it or its from some book? [b] what do you expect it to do? What is the output you want?
• user3643513: nodelist [<custom.binary_tree_preorder.Node instance at 0x03CFCD00>, <custom.binary_tree_preorder.Node instance at 0x03CEEBE8>, <custom.binary_tree_preorder.Node instance at 0x03CEED50>, <custom.binary_tree_preorder.Node instance at 0x03D04530>, <custom.binary_tree_preorder.Node instance at 0x03D045A8>, <custom.binary_tree_preorder.Node instance at 0x03D04800>, <custom.binary_tree_preorder.Node instance at 0x03D04788>, <custom.binary_tree_preorder.Node instance at 0x03D044E0>,.....] This is what it is printing. I want the list that I have, to be printed in the form of a binary tree.
• Burhan Khalid: What is Node, and you are going to have to give a lot more details to go further.

Answer 1

"I tried the following code but I am not sure what it is doing." is brilliant. Where did you get that code? What should it do?

Do you want a binary tree or is it a sorted binary tree? Should the tree have bounded or minimal depth?

Your algorithm seems to be converting to a double linked list. If my limited experience in python doesn't stop me from noticing a really strange exceptional/border case it's equivalent to:

nodelist = [Node(c) for c in list]
for i in range(len(list)):
 if i != 0:
 nodelist[i].left = nodelist[i-1]
 if i != len(list) - 1:
 nodelist[i].right = nodelist[i+1]
for n in nodelist:
 print unicode(n)

First block converts the list of numbers to a list of nodes containing the numbers. Second block runs through the list linking all but the left-most node to its left and all but the right-most to its right. Last block prints the list of nodes that now form a double linked list.

By the way your double-linked list can be interpreted as unsorted binary tree of maximal depth. But in this interpretation "left" is a strangely named reference to the parent, which means that you may be missing an empty reference for each non-existant left child.