Binary Tree in Python

Question

This is my code-snippet for a Binary Tree implementation in Python. This WORKS when I run the PreOrder function.

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

class BinaryTree(Node):
    def __init__(self):
        self.root = None

    def addNode(self,data):
        return Node(data)

    def insert(self,root,data):
        if(root == None):
            root = self.addNode(data)
        else:
            if(data <= root.data):
               root.left = self.insert(root.left,data)
            else:
                root.right = self.insert(root.right,data)
        return root

    def PreOrder(self,root):
        if root == None:
            pass
        else:
            print(root.data)
            self.PreOrder(root.left)
            self.PreOrder(root.right)



a = BinaryTree()
root = a.addNode(2)
#root = None
a.insert(root,4)
a.insert(root,34)
a.insert(root,45)
a.insert(root,46)
a.insert(root,41)
a.insert(root,48)
a.PreOrder(root)

However changing the 2nd and the 3rd lines in main to

#root = a.addNode(2)
root = None

doesn't print anything. I feel I am missing out on something basic here. Any clarifications will be gratefully appreciated.

You have a self.root attribute but never assign to it, then keep passing around an explicit root. Why not just do self.root = and use self.root throughout? — Martijn Pieters
– Martijn Pieters, Commented Jan 21, 2013 at 13:27
Why do people keep telling Binary Tree where they really mean Binary Search Tree? — QuestionEverything
– QuestionEverything, Commented Jul 6, 2017 at 20:21

Community · Accepted Answer · 2017-05-23 10:29:39Z

8

You're passing None to your function, which you defined with:

if root == None:
    pass

That is why nothing gets printed.

Also, this is just a personal view, I would actually make PreOrder accept only the self argument, and do the PreOrder from there, making it very simple to define recursively.

Basically something like:

 def PreOrder(self):
     print self.data 
     if self.left:
          print self.left.PreOrder()
     if self.right:
          print self.right.PreOrder()

But this is a matter of preference, your solution works just fine.

As blatant promotion, I actually wrote a post about writing a basic BinaryTree in Python recently, if you care to check it out, it can be found here:

http://intothewebs.tumblr.com/post/40256328302/embrace-the-basics-binary-tree

UPDATE:

Ok, after you comment, I understand your doubt.

The root parameter that is passed into your method isn't really changed, because params in Python are passed by value:

How do I pass a variable by reference?

Read the accepted answer in this question, it's awesome and should explain what I mean by that.

Of you have:

root = None
a = a.insert(root,4)
a.insert...

And so forth, your code should work.

edited May 23, 2017 at 10:29

CommunityBot

11 silver badge

answered Jan 21, 2013 at 13:23

pcalcao

16k1 gold badge49 silver badges65 bronze badges

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

1 Comment

Bayko Over a year ago

Sorry if I wasnt clear in the question. After changing to "root = None" I still have it followed by a.Insert(root,4) and so forth. So how is root none when I enter the PreOrder function?

hd1 · Accepted Answer · 2013-01-21 13:23:48Z

1

You have root = None and then in PreOrder your first line is if root == None: pass so it isn't going to do anything for you.

answered Jan 21, 2013 at 13:23

hd1

34.9k5 gold badges83 silver badges95 bronze badges

Comments

Chamath Silva · Accepted Answer · 2014-12-17 10:49:18Z

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

class BinaryTree:

    def __init__(self):
        self.root = None


    def insert_node(self,root,element):
        if self.root is None:
            self.root = Node(element)
        else:

            if root is None:
                root = Node(element)
            elif root.data <= element:
                root.right = self.insert_node(root.right,element)
            elif root.data > element:
                root.left = self.insert_node(root.left,element)


        return root

    def PreOrder(self,root):
        if root is not None:
            print(root.data)
            if root.left is not None:
                self.PreOrder(root.left)
            if root.right is not None:
                self.PreOrder(root.right)



a = BinaryTree()
a.insert_node(a.root,3)
a.insert_node(a.root,4)
a.insert_node(a.root,34)
a.insert_node(a.root,45)
a.insert_node(a.root,46)
a.insert_node(a.root,2)
a.insert_node(a.root,48)
a.PreOrder(a.root)

Collectives™ on Stack Overflow

Binary Tree in Python

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related