Binary Search Tree is a tree data structure where binary tree is either empty or non-empty. if it is non-empty then every node contains a key which is distinct and satisfies the following properties:

Values less than its parents are places at left side of the parent node.
Values greater than its parent are placed at right side of the parent node.
The left and right subtree of are given again binary search trees.

In this article we going to implement binary search tree in python language. Binary Search Tree we are going to implement it with linked nodes and not a array.

Binary Search Tree In Python

So first we will create a node class and then a binary tree class. After that we will implement some methods to the binary tree

List of methods that we will implement in the binary tree are :

insert
preOrder treversal
postOrder treversal
inOrder treversal
levelOrder treversal
height of the tree

Code: Node Class of binary search tree

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

Code: Binary Tree class for binary Search tree

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

Code: Methods in the binary search tree

    #inserts a node in binary tree
    def insert(self,data):
        if(self.root == None):
            self.root = Node(data)
        else:
            self.insertNode(data,self.root)
    #inserts a node in binary search tree
    def insertNode(self,data,node):
        if(data < node.data):
            if(node.left == None):
                node.left = Node(data)
            else:
                self.insertNode(data,node.left)
        else:
            if(node.right == None):
                node.right = Node(data)
            else:
                self.insertNode(data,node.right)

    #preOrder treversal of binary tree print data in one line
    def preOrder(self,root):
        if(root != None):
            print(root.data,end=" ")
            self.preOrder(root.left)
            self.preOrder(root.right)

    #postOrder treversal of binary tree print data in one line
    def postOrder(self,root):
        if(root != None):
            self.postOrder(root.left)
            self.postOrder(root.right)
            print(root.data,end=" ")

    #inOrder treversal of binary tree print data in one line
    def inOrder(self,root):
        if(root != None):
            self.inOrder(root.left)
            print(root.data,end=" ")
            self.inOrder(root.right)

    # level order traversal of binary tree
    def levelOrder(self,root):
        queue = []
        queue.append(root)
        while(len(queue) > 0):
            node = queue.pop(0)
            print(node.data,end=" ")
            if(node.left != None):
                queue.append(node.left)
            if(node.right != None):
                queue.append(node.right)

    def height(self,root):
        add = 0
        if root.left:
            add = 1 + self.height(root.left)
        if root.right:
            add = 1 + self.height(root.right)
        return add

Now lets initialize the binary search tree.

#create a binary tree
tree = binaryTree()
#inserting nodes in binary tree using insertNode() method
# inserting 10 nodes using loop
for i in range(10):
    tree.insert( ceil(random() * 100) )
#preOrder treversal
print("PreOrder Traversal of binary tree is:")
tree.preOrder(tree.root)
print()
#postOrder treversal
print("PostOrder Traversal of binary tree is:")
tree.postOrder(tree.root)
print()
#inOrder treversal
print("InOrder Traversal of binary tree is:")
tree.inOrder(tree.root)
print()
#level order traversal
print("LevelOrder Traversal of binary tree is:")
tree.levelOrder(tree.root)
print()
#height of binary tree
print("Height of binary tree is:")
print(tree.height(tree.root))
print()

After running the above code we get the following output

Output:

PreOrder Traversal of binary tree is:
64 31 3 13 11 10 51 48 72 95
PostOrder Traversal of binary tree is:
10 11 13 3 48 51 31 95 72 64
InOrder Traversal of binary tree is:
3 10 11 13 31 48 51 64 72 95
LevelOrder Traversal of binary tree is:
64 31 72 3 51 95 13 48 11 10
Height of binary tree is:
3