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.
- All the nodes on the left of a current node has a value less than current node.
- 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.
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
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 & 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()
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
