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.

Level order traversal of a binary tree.
Level order traversal of a binary tree.

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.


Gaurav Yadav

Gaurav is cloud infrastructure engineer and a full stack web developer and blogger. Sportsperson by heart and loves football. Scale is something he loves to work for and always keen to learn new tech. Experienced with CI/CD, distributed cloud infrastructure, build systems and lot of SRE Stuff.

5 COMMENTS
  • Manoj Kumar
    Reply

    Good Job Gaurav !
    Welcome to My Blog

    http://www.computersciencejunction.in

    1. Gaurav Yadav
      Reply

      Thanks Manoj.

  • Major algorithms asked during Interviews. - Learn Steps
    Reply

    […] Algorithms: Binary Search Tree and its functionality in python […]

  • Madjayhawk
    Reply

    Does not run.

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

    1. Gaurav Yadav
      Reply

      What does it says can you show me the error?

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.