How to implement Binary Search Tree in Python [Easy Examples]

Implement Binary Search Tree in Python - Introduction

A Tree is a non linear data structure in which nodes are connected in a hierarchical manner. Every tree has one root node that marks the access point of all the other nodes in the tree. So, a Tree is formed of one root node, and 0 or more child nodes.

 

Binary Search Tree

Binary search tree is a special binary tree that consist of 0, 1 or 2 child nodes and follows certain rules while inserting the value in the node. The Binary search tree is a binary tree in which all the nodes follow the below mentioned properties.

Advertisement
  1. All the nodes on the left of a current node has a value less than current node.
  2. All the nodes on the right of a current node has a value greater than current node.

The figure below shows the structure of Binary search Tree.
Binary search Tree
Here, we will see how to implement insertion, deletion and traversal operation in binary search tree from scratch in Python.

 

Creating a node

In order to create a binary tree in Python, we will have to first create a Node class that represents a single node. This Node class will have 3 class variables. The left variable pointing to the left child, the right variable pointing to the right child and the data variable containing the actual value for that node. The code below shows the class representing a node.

# Implement binary search tree create node
# Creating a class for node object
class Node(object):
    # Initializing to None
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

 

Implement Binary Search Tree - Insertion function

In order to insert a node in binary search tree, we need to make sure that none of the properties of binary search tree is violated while inserting a node.
Here, the each call to the insertion method will insert one node to a binary search tree. The first call to insertion will make that node as a root node. All the other insertions will take place considering the value of root node.
The code below shows the insertion function which places the node in a tree such that none of the properties of binary search tree is violated.

# Implement binary search tree insert function
# Creating a class for node object
class Node(object):
    # Initializing to None
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

# Inserting a node in Binary search tree
def insertion(val):
    # Condition if this is a first node then it will be considered as a root
    if(root.data==None):
        print(val," Inserted as root")
        root.data=val
    # Else part will be executed for all the other insertions
    else:
        # Pointer to move around tree to search for a place of new node
        p=root
        
        # Creating a new node and writing a value in the data part
        n = Node()
        n.data=val
        
        # Iterating to search for an appropriate place of new node
        while(1):
            # if val is less than the current node p indicates that new node will be inserted on left subtree
            if(val<p.data):
                if(p.left==None):
                    print(val," Inserted on left of ",p.data)
                    p.left=n
                    break
                else:
                    p=p.left
            # if val is greater than the current node p indicates that new node will be inserted on right subtree
            else:
                if(p.right==None):
                    print(val," Inserted on right of",p.data)
                    p.right=n
                    break
                else:
                    p=p.right

root = Node()  
insertion(10)
insertion(5)
insertion(20)
insertion(30)
insertion(25)
insertion(2)
'''
           10
          /  \
         5   20
        /      \
       2       30
              /
             25
'''

Output

10  Inserted as root
5  Inserted on left of  10
20  Inserted on right of 10
30  Inserted on right of 20
25  Inserted on left of  30
2  Inserted on left of  5

 

Implement Binary Search Tree - Inorder Traversal

Traversing a tree means iterating over all nodes in some sequence. As the tree is not a linear data structure, there will be more than one possible next node from a current node, so some nodes will be stored so that we can visit them later. The Inorder traversal is one of the depth first tree traversal methods. Here, while traversing a tree, whenever we come across a node for the first time, we recursively traverse to its left sub tree before printing the current node, and then recursively traverse to its right subtree thereafter.
Once insertion is done in binary search tree, we can add the recursive function given below to traverse a tree in inorder sequence.

# Implement binary search tree inorder traversal function
# Function for inorder traversal of tree
def inorder(node):
    if node:
	# Traversing left subtree
        inorder(node.left)
	# Visiting node
        print(node.data)
	# Traversing right subtree
        inorder(node.right)

Output

Advertisement
2
5
10
20
25
30

 

Implement Binary Search Tree - Deletion function

In order to implement binary search tree delete function, we need to make sure that none of the properties of binary search tree is violated while deleting a node. Here, the each call to the deletion method will delete one node from a binary search tree.
The code below shows the deletion function that has different set of codes for considering each cases like deletion of leaf node, internal node with one child and node with a two childs. This deletion is done in such a way that none of the properties of binary search tree is violated.

# Implement binary search tree deletion function
def deletion(value):
    # If tree is empty
    if(root == None):
        print ("Tree is empty")
        
    # Initializing the pointers to traverse a tree
    p=root
    q=root
    
    # Searching for a node to be deleted
    while(1):
        if(value > p.data):
            q=p
            p=p.right
        elif(value < p.data ):
            q=p
            p=p.left
        else:
            break

    # If the desired node is a leaf node this condition will be true
    if(p.left==None and p.right==None):
	    if(q.left==p):
		    q.left=None
	    else:
		    q.right=None
	    print("Value deleted from leaf")
	    return p.data
	

	#deletion of node with one child on right
    if(p.left==None and p.right!=None):
        print("\ndeleting node having only right subtree")
        if(q.left==p):
            q.left=p.right
        else:
            q.right=p.right
        return p.data

    # Deletion of node with one child on left
    if(p.left!=None and p.right==None):
        print("\ndeleting node having only left subtree")
        if(q.left==p):
            q.left=p.left
        else:
            q.right=p.left
        return p.data


	#deletion of node having 2 childs
    if(p.left!=None and p.right!=None):
        temp=p
        temp1=p.right
        while(temp1.left!=None):
            temp=temp1
            temp1=temp1.left
    if(temp1==temp.left):
        print("\ndeleting node having two childs & right subtree")
        temp.left=temp1.right
    else:
        print("\ndeleting node having two childs & Only right node ")
        temp.right=temp1.right
        p.data=temp1.data
        return value

root = Node()  
print("Value ",deletion(25),"deleted successfully")
print("Value ",deletion(10),"deleted successfully")
'''
           10
          /  \
         5   20
        /      \
       2       30
              /
             25
'''

Output

Value deleted from leaf
Value  25 deleted successfully
Found desired node

deleting node having two childs & Only right node 
Value  10 deleted successfully

 

Sample Code

Here is the complete code for reference:

# Creating a class for node object
class Node(object):
    # Initializing to None
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

# Inserting a node in Binary search tree
def insertion(val):
    # Condition if this is a first node then it will be considered as a root
    if(root.data==None):
        print(val," Inserted as root")
        root.data=val
    # Else part will be executed for all the other insertions
    else:
        # Pointer to move around tree to search for a place of new node
        p=root
        
        # Creating a new node and writing a value in the data part
        n = Node()
        n.data=val
        
        # Iterating to search for an appropriate place of new node
        while(1):
            # if val is less than the current node p indicates that new node will be inserted on left subtree
            if(val<p.data):
                if(p.left==None):
                    print(val," Inserted on left of ",p.data)
                    p.left=n
                    break
                else:
                    p=p.left
            # if val is greater than the current node p indicates that new node will be inserted on right subtree
            else:
                if(p.right==None):
                    print(val," Inserted on right of",p.data)
                    p.right=n
                    break
                else:
                    p=p.right

def inorder(node):
    if node:
	# Traversing left subtree
        inorder(node.left)
	# Visiting node
        print(node.data)
	# Traversing right subtree
        inorder(node.right)
def deletion(value):
    # If tree is empty
    if(root == None):
        print ("Tree is empty")
        
    # Initializing the pointers to traverse a tree
    p=root
    q=root
    
    # Searching for a node to be deleted
    while(1):
        if(value > p.data):
            q=p
            p=p.right
        elif(value < p.data ):
            q=p
            p=p.left
        else:
            break

    # If the desired node is a leaf node this condition will be true
    if(p.left==None and p.right==None):
	    if(q.left==p):
		    q.left=None
	    else:
		    q.right=None
	    print("Value deleted from leaf")
	    return p.data
	

	#deletion of node with one child on right
    if(p.left==None and p.right!=None):
        print("\ndeleting node having only right subtree")
        if(q.left==p):
            q.left=p.right
        else:
            q.right=p.right
        return p.data

    # Deletion of node with one child on left
    if(p.left!=None and p.right==None):
        print("\ndeleting node having only left subtree")
        if(q.left==p):
            q.left=p.left
        else:
            q.right=p.left
        return p.data


	#deletion of node having 2 childs
    if(p.left!=None and p.right!=None):
        temp=p
        temp1=p.right
        while(temp1.left!=None):
            temp=temp1
            temp1=temp1.left
    if(temp1==temp.left):
        print("\ndeleting node having two childs &amp; right subtree")
        temp.left=temp1.right
    else:
        print("\ndeleting node having two childs &amp; Only right node ")
        temp.right=temp1.right
        p.data=temp1.data
        return value


root = Node()  
insertion(10)
insertion(5)
insertion(20)
insertion(30)
insertion(25)
insertion(2)

print("Value ",deletion(25),"deleted successfully")
print("Value ",deletion(10),"deleted successfully")

 

Summary

The knowledge of how to implement binary search tree in Python is very useful while working on real time applications. In many situations, we will need to perform the operations on binary search tree in Python. In this tutorial, we covered creation, insertion, deletion and traversal on binary search tree with the sample code example. We learned in detail about this with an example. All in all, this tutorial, covers everything that you need to know in order to implement binary search tree in Python.

 

References

Classes in Python

 

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment