CODEWITHSUNDEEP
pythonpython-3.xbinary-search-tree
spunkyquagga
spunkyquagga

Reputation: 91

Binary search tree: insert operation

I have the following code that implements BST. But when I try to insert elements by calling insert function, it only prints out 10 and 15. can someone provide suggestions/corrections?

class Node:
    def __init__(self,val):
        self.rightchild = None
        self.leftchild = None
        self.root = None
        self.value=val

    def insert(self,data):
        if self.value == data:
            return False

        elif self.value > data:
            if self.leftchild:
                return self.leftchild.insert(data)
            else:
                self.leftchild = Node(data)
                return True
        else:
            if self.rightchild:
                return self.rightchild.insert(data)
            else:
                self.rightchild = Node(data)
                return True

    def find(self,data):
        if self.value == data:
            return True
        elif self.value > data:
            if self.leftchild:
                return self.leftchild.find(data)
            else:
                return False
        else:
            if self.rightchild:
                return self.rightchild.find(data)
            else:
                return False

    def inorder(self):        
        if self.root:
            return self.leftchild.inorder()
        print(str(self.value))
        if self.rightchild:
            return self.rightchild.inorder()

class BST:    
    def __init__(self):
        self.root=None

    def insert(self,data):
        if self.root:
            return self.root.insert(data)
        else:
            self.root = Node(data)
            return True

    def find(self,data):
        if self.root:
            return self.root.find(data)
        else:
            return False

    def inorder(self):
        if self.root:
            self.root.inorder()

bst = BST()
bst.insert(10))
bst.insert(5)
bst.insert(15)
bst.insert(8)
bst.inorder()

Upvotes: 0

Views: 36

Answers (1)

Ray Toal
Ray Toal

Reputation: 88378

In Node#inorder you have a typo. The first line should read

if self.leftchild:

Also, you are returning prematurely. Don't return in inorder because this method is printing, not computing anything. Rewrite to:

def inorder(self):
   if self.leftchild:
       self.leftchild.inorder()
   print(str(self.value))
   if self.rightchild:
        self.rightchild.inorder()

After making these fixes, I was able to get the expected answer:

$ python3 bst.py
5
8
10
15

Upvotes: 1

Related Questions