Algorithms: Binary Search Tree and its functionality in python

Back in the algorithms section with python we are going to see how we can code Binary Search Tree and its functionality in python. Binary search tree are binary tree where the left child is less than root and right child is greater than root. We will be performing insertion, searching, traversal, min and other functions. Read more about them here.

Binary Search Tree and its functionality in python

Lets look at the code below.

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


def insert(root, data):
   if root.data > data:
       if root.left:
           insert(root.left,data)
       else:
           tmp = Node(data)
           root.left = tmp
       elif root.data < data:
           if root.right:
               insert(root.right,data)
           else:
               tmp = Node(data)
               root.right = tmp
       else:
           print "Key already exist"


def in_order(root):
   if root:
       in_order(root.left)
       print root.data,
       in_order(root.right)


def search(root,key):
    if root:
        if root.data == key:
            return True
        elif root.data < key:
            return search(root.right, key)
        else:
            return search(root.left, key)
    return False 


def get_min(root):
   while root.left:
       root = root.left
   return root.data


def get_max(root):
   while root.right:
       root = root.right
   return root.data


a = Node(4)
insert(a,2)
insert(a,5)
insert(a,1)
insert(a,3)
insert(a,8)
in_order(a)


print search(a,8)
print search(a,2)
print search(a,23)
print get_max(a)
print get_min(a)

What we did here:

Node class to make the nodes of binary search tree.

Then insert functions, what this function is doing is checking if the data is lesser than node then moves to left child else moves to right child and place it at the end.

Search function again works same as insert functions. The only difference is in this we are getting and telling if the data is present while in insert we are adding node to the true.

In order traversal to visit all the node. Do you know in order traversal of binary search tree is in sorted order.

Get min and Get max functions to get the minimum and maximum of the Binary Search Tree.

Delete I am leaving delete function for you. If you are stuck comment below and I will write a delete function for you.

Liked the article, Please share and subscribe.

Also if you want to read more about algorithms read here.