Binary tree with python

Question

I don't understand where am I making a mistake, the following is the code for creating a tree but it never creates the tree. I think there is some logical mistake in the make_tree function.

    class node:

    def __init__(self, a):
        self.a=a
        self.l=None
        self.r=None


class tree:
    def __init__(self, a,maxd=5):
        self.s=node(a)
        self.maxd=maxd

    def make_tree(self, n,d=0):

        if(self.maxd<d):
            return n
        else:

            n=node(d)
            n.a=d
            self.make_tree( n.l,d+1)
            self.make_tree(n.r,d+1)

            return n

t=tree(2)
t.s=t.make_tree(t.s)
print 'children ', (t.s.r!=None), (t.s.l!=None)

output:

children False False

want a tree like this:

     o
   /   \
  o     o
/  \   / \
o   o  o  o

The left and right children of t.s are None in this case, which is why you're getting that output. What is the desired output? — inspectorG4dget
– inspectorG4dget, Commented Mar 21, 2016 at 20:43
yes they are None, but I am creating new node in make-tree function, so after calling make_tree function tree should be created. — someone
– someone, Commented Mar 21, 2016 at 20:45
You're calling make_tree on the created node several times. Each time that node is created, its left and right are set to None, according your Node's __init__. It might help to have a diagram of what you want the tree to look like — inspectorG4dget
– inspectorG4dget, Commented Mar 21, 2016 at 20:47
when I recursively call make_tree function with left node and right node as input it creates new node in else part for them. so shouldn't it work? and make a tree. like normal binary tree of given depth — someone
– someone, Commented Mar 21, 2016 at 20:51

Blckknght · Accepted Answer · 2016-03-21 21:29:40Z

1

I think you're expecting the line:

n=node(d)

to do more than it can do in Python. That line rebinds the local name n, but it doesn't change where the original n value came from in the calling code.

I think you should skip passing n to the make_tree function entirely and simply use its return value instead:

def make_tree(self, d=0):
    if d > self.maxd:
        return None
    n = Node(d)
    n.l = self.make_tree(d+1)
    n.r = self.make_tree(d+1)
    return n

You'd call it with something like:

tree.s = tree.make_tree()

Of course, make_tree could be a regular function rather than a method, since it only uses self to call itself recursively.

answered Mar 21, 2016 at 21:29

Blckknght

106k11 gold badges135 silver badges188 bronze badges

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

Collectives™ on Stack Overflow

Binary tree with python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related