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.

What is the list input of the function you want to make, and the expected tree output? — ddaa
– ddaa, Commented Jan 16, 2010 at 19:37
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? — Roman
– Roman, Commented Jan 16, 2010 at 19:39
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. — Laurence Gonsalves
– Laurence Gonsalves, Commented Jan 16, 2010 at 19:40
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. — MAK
– MAK, Commented Jan 16, 2010 at 19:46

danben · Accepted Answer · 2010-01-16 19:48:44Z

1

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

This could be done even if your triangle were written as a list, like 0 1 2 3 4 5 6 7 8 9
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).

answered Jan 16, 2010 at 19:48

danben

83.8k18 gold badges126 silver badges149 bronze badges

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

2 Comments

johne Over a year ago

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 Over a year ago

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?

Antony Hatchkins · Accepted Answer · 2010-01-16 20:11:15Z

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)

Collectives™ on Stack Overflow

generating a binary tree from given data in python

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related