Binary Search Tree

Binary Search Tree 

Binary search tree is a binary tree where node values greater than root node are placed towards right side of root and node values less than or equal to root node are placed towards left side of root.

Source Code:

class Node:
    def __init__(self,data):
        self.data=data
        self.rchild=None
        self.lchild=None
class Bst:
    def __init__(self):
        self.root=None             
 
    def createtree(self,data):
        if self.root==None:
            self.root = Node(data)
        else:
            temp = self.root
            while temp !=None:
                if data < temp.data:
                    if temp.lchild==None:
                        temp.lchild = Node(data)
                        return
                    else:
                        temp = temp.lchild
                else:
                    if temp.rchild==None:
                        temp.rchild = Node(data)
                        return
                    else:
                        temp = temp.rchild
     
    def inorder(self, root):
        if root!=None:
            self.inorder(root.lchild)
            print(root.data)
            self.inorder(root.rchild)
 
    def preorder(self, root):
        if root!=None:
            print(root.data)
            self.preorder(root.lchild)         
            self.preorder(root.rchild)
         
    def postorder(self,root):
        if root!=None:
            self.postorder(root.lchild)         
            self.postorder(root.rchild)
            print(root.data)

    def display(self,root):
        if root!=None:         
            print(root.data)
            self.inorder(root.rchild)
            self.inorder(root.lchild)
         
    def count(self, root):
        if root == None:
            return 0
        else:
            return 1 + self.count(root.lchild) + self.count(root.rchild)

def menu():
    global ch
    print("\n1.create\n2.preorder\n3.postorder\n4.inorder
                   \n5.display\n6.count\n7.stop")
    ch=int(input("enter u r choice"))

t=Bst()
while True:
    menu()
    if ch==1:
         n=int(input("enter no of node for tree"))
         for i in range(n):
            data=int(input("enter data"))
            t.createtree(data)
    elif ch==2:
       print("preorder")
       t.preorder(t.root)
    elif ch==3:
       print("postorder")
       t.postorder(t.root)
    elif ch==4:
       print("inorder")
       t.inorder(t.root)
    elif ch==5:
       t.display(t.root)
    elif ch==6:
        print("number of nodes in binary search tree")
        print(t.count(t.root))
    else:
        exit(0)
 

 

 


 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice1
enter no of node for tree3
enter data20
enter data10
enter data30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice2
preorder
20
10
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice3
postorder
10
30
20

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice4
inorder
10
20
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice5
20
30
10

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice6
number of nodes in binary search tree
3

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice7
>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html