CODEWITHSUNDEEP
pythonbinary-search-tree
Kishor
Kishor

Reputation: 450

Not getting required results in binary search tree(BST) in python

I had made binary trees in C++ and was trying to make a BST in python so I wrote the code as shown below.But, nothing gets displayed! I don't know what is happening. 

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


class Tree:
    def __init__(self):
        self.root = None
        pass

    def createNode(self, val):
        return Node(val)

    def insert(self, value):
        self.__insert(self.root, value)

    def __insert(self, rootptr, val):
        if rootptr is None:
            rootptr = self.createNode(val)
            return 0

        elif val < rootptr.value:
            if rootptr.left is not None:
                self.__insert(rootptr.left, val)
            else:
                rootptr.left = self.createNode(val)

        elif val > rootptr.value:
            if rootptr.right is not None:
                self.__insert(rootptr.right, val)
            else:
                rootptr.right = self.createNode(val)

        else:
            #TODO: raise exception
            print("Duplicate value!")



    def traversePreorder(self):
        self.__traversePreorder(self.root)

    def __traversePreorder(self, rootptr):
        if rootptr is None:
            return 1
        print(rootptr.value)
        self.__traversePreorder(rootptr.left)
        self.__traversePreorder(rootptr.right)




mytree = Tree()
mytree.insert(1)
mytree.insert(2)
mytree.insert(2)
mytree.insert(4)
mytree.insert(5)
mytree.traversePreorder()

I tried a lot of tweaks here and there but to my frustration nothing worked.Any help would be appreciated.Thank you.

Upvotes: 0

Views: 37

Answers (1)

VPfB
VPfB

Reputation: 17267

You are trying to use a pointer like in C (call by reference) which will not work in Python.

When the very first element is going to be inserted into a new empty tree:

mytree.insert(1)

the method insert is called. It is defined as follows:

def insert(self, value):
    self.__insert(self.root, value)

The root is not set yet, i.e. self.root is None. This None value is passed to __insert as rootptr

def __insert(self, rootptr, val):
    if rootptr is None:
        rootptr = self.createNode(val) # <== this will not change self.root !!
        return 0

But as you see in the attached comment, setting rootptr only changes this local variable.

You can think of a variable as a label that has a name on it, which you tie onto a value. (source: This tutorial)

Upvotes: 1

Related Questions