generating a binary tree from given data in python

Question

i wanted to know how to read values from a list into a binary tree. i have a triangle like this:

 0
 1 2
 3 4 5
 6 7 8 9

i have written a class node like this

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

basically what i want to do is something like this

node(0,node(1),node(2))

i want to make a recursive function that can handle much bigger triangles. Can somehow tell me what i am supposed to do?

edit: quite clearly binary tree is not the way to approach this problem. what i basically want to find out are all the different combination's from top to bottom. like 0,1,3,6 0,2,5,8 etc.

• Antony Hatchkins: shouldn't it be tagged a homework?
• ddaa: What is the list input of the function you want to make, and the expected tree output?
• Roman: This looks like functional code. I would capitalize to Node so that it follows the standard for naming a class (right now it looks like a function). What exactly is the problem?
• Laurence Gonsalves: It's unclear whether that "triangle" is actually a binary tree, because you don't show any of the edges (connections between nodes). Which node is 7's parent? 3? 4? Both? If both, then this isn't a tree.
• MAK: I doubt recursion is the way to go here. As far as I understand, you need to process the nodes in a first-in-first-out manner (hint:use a queue). This also does not look like a binary tree - nodes can have two parents.

Answer 1

This does sound like homework, so I won't write code, but here are a couple of hints:

1. This could be done even if your triangle were written as a list, like 0 1 2 3 4 5 6 7 8 9

2. Because it seems like this is a full binary tree (assuming your triangle is wrong and the third row is actually supposed to be 3 4 5 6), you could maintain a parents queue whose head is the next parent that needs children. Note that I am specifically not recommending recursion.

A full binary tree is one where each non-leaf node has exactly two children. If this is not supposed to be a full binary tree, then there is no deterministic way to interpret the problem (since each of node 1 and 2 could have 1 or 2 children, given your picture).

• johne: i am new to this site so i dont know if help on puzzles from projecteuler are banned, i am sorry if it is. the solution to this problem is available on the pyeuler site, but i could not understand anything. the structure of the triangle gave me the impression that it could be solved using trees, so i thought of trying out my theory and hit a dead end.
• danben: No, it's not banned. But the specification of the problem as you have it seems odd. Do you have a link, or better yet, can you recheck the problem statement and revise?

Answer 2

For such list:

a = 'aBCdef'

The program below generates the following structure:

- a -
- B C
B C -
- d e
d e f
e f -

Code (input list is assumed to correspond to a 'complete' triangular):

class Node:
 def __init__(self,data,left=None,right=None):
 self.data=data
 self.left=left
 self.right=right
 def __unicode__(self):
 return '%s %s %s' % (
 self.left.data if self.left or '-', 
 self.data, 
 self.right.data if self.right or '-')
nodelist = [Node(c) for c in a]
i,y = 0,1
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(a):
 y+=1
 else:
 break
for n in nodelist:
 print unicode(n)