Binary Search Tree is a kind of tree in which each node follows specific properties to construct a tree.
Properties of Binary Search Tree
At every level, the left sub tree is smaller than its parent root key.
At every level, the right sub tree is larger than its parent root key.
It is called Binary Tree because it has at most 2 children at every parent node.
It is also called a sorted ordered binary tree or search tree. It is called search tree because the search or find operation for a key requires O(log(n)) time complexity.
Operations in Binary Search Tree
Insertion
Search
Traversal (Preorder, Inorder, Postorder)
Implementation of Binary Search Tree
Now, let’s start creating a Binary Search Tree. So for every key of the tree, we require a Node which consists of data, left child pointer, and then right child pointer.
Create Class Node
class Node(object):
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
1. Insert Operation
Now after initializing a Node class, let’s create an Insert operation that will insert the key either to the left of the parent or the right of the parent.
def insert(self, data):
if self.data == data:
return False # As BST cannot contain duplicate data
elif data < self.data:
''' Data less than the root data is placed to the left of the root '''
if self.leftChild:
return self.leftChild.insert(data)
else:
self.leftChild = Node(data)
return True
else:
''' Data greater than the root data is placed to the right of the root '''
if self.rightChild:
return self.rightChild.insert(data)
else:
self.rightChild = Node(data)
return True
2. Find Operation
After creating the Insert Operation, let’s create a find or Search operation which checks whether the specified data is in the tree or not.
Now we have implemented Insertion and Search Operation for our Binary Search Tree.
Now we have to implement the traversal of the BST. So, there are 3 different types of Traversal in BST.
1. Preorder Traversal
Preorder Traversal is a kind of traversal in which first we print the parent root and then traverse to the left of the parent and after completing the whole left branch then proceed to the right of the parent root at every level.
def preorder(self):
'''For preorder traversal of the BST '''
if self:
print(str(self.data), end = ' ')
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()
2. Inorder Traversal
Inorder Traversal is similar to Preorder Traversal but the difference is first we go to the extreme left and then we print the parent and then we procees to the right of the parent at every level.
And Inorder Traversal always prints the BST in Sorted Order.
def inorder(self):
''' For Inorder traversal of the BST '''
if self:
if self.leftChild:
self.leftChild.inorder()
print(str(self.data), end = ' ')
if self.rightChild:
self.rightChild.inorder()
3. PostOrder Traversal
PostOrder Traversal is similar to other traversals but the difference is first we go the extreme left then we proceed to the right and then we print out the parent of the key at every level.
def postorder(self):
''' For postorder traversal of the BST '''
if self:
if self.leftChild:
self.leftChild.postorder()
if self.rightChild:
self.rightChild.postorder()
print(str(self.data), end = ' ')
Now we have to implement Node Class, let’s implement the Tree Class which instantiates Node Class and its operations.
Create Tree Class
We first create a similar function that we have created in Node class to expose Tree Class functionalities to outside and not Node Class directly.
class Tree(object):
def __init__(self, initial_data = []):
self.root = None
# If provided, add initial data
for data in initial_data:
self.insert(data)
def insert(self, data):
if self.root:
return self.root.insert(data)
else:
self.root = Node(data)
return True
def find(self, data):
if self.root:
return self.root.find(data)
else:
return False
def preorder(self):
if self.root is not None:
print()
print('Preorder: ')
self.root.preorder()
def inorder(self):
print()
if self.root is not None:
print('Inorder: ')
self.root.inorder()
def postorder(self):
print()
if self.root is not None:
print('Postorder: ')
self.root.postorder()
Print Complete Tree
Let’s add one more functionality to our class Tree which prints the whole tree in the console log output.
def pprint(self, head_node=0, _pre="", _last=True, term=False):
head_node = self.root if head_node == 0 else head_node
data = "*" if head_node is None else head_node.data
print(_pre, "`- " if _last else "|- ", data, sep="")
_pre += " " if _last else "| "
if term: return
for i, child in enumerate([head_node.leftChild, head_node.rightChild]):
self.pprint(child, _pre, bool(i) ,term=not(bool(child)))
Implement Main Function
Now our BST is implemented perfectly in the above classes. Let’s create an object of Tree Class and then check its functionalities.
classNode(object):def__init__(self,data): self.data = data self.leftChild =None self.rightChild =Nonedefinsert(self,data):if self.data == data:returnFalse# As BST cannot contain duplicate dataelif data < self.data:''' Data less than the root data is placed to the left of the root '''if self.leftChild:return self.leftChild.insert(data)else: self.leftChild =Node(data)returnTrueelse:''' Data greater than the root data is placed to the right of the root '''if self.rightChild:return self.rightChild.insert(data)else: self.rightChild =Node(data)returnTruedeffind(self,data):if(data == self.data):returnTrueelif(data < self.data):if self.leftChild:return self.leftChild.find(data)else:returnFalseelse:if self.rightChild:return self.rightChild.find(data)else:returnFalsedefpreorder(self):'''For preorder traversal of the BST '''if self:print(str(self.data), end =' ')if self.leftChild: self.leftChild.preorder()if self.rightChild: self.rightChild.preorder()definorder(self):''' For Inorder traversal of the BST '''if self:if self.leftChild: self.leftChild.inorder()print(str(self.data), end =' ')if self.rightChild: self.rightChild.inorder()defpostorder(self):''' For postorder traversal of the BST '''if self:if self.leftChild: self.leftChild.postorder()if self.rightChild: self.rightChild.postorder()print(str(self.data), end =' ')classTree(object):def__init__(self,initial_data= []): self.root =None# If provided, add initial datafor data in initial_data: self.insert(data)definsert(self,data):if self.root:return self.root.insert(data)else: self.root =Node(data)returnTruedeffind(self,data):if self.root:return self.root.find(data)else:returnFalsedefpreorder(self):if self.root isnotNone:print()print('Preorder: ') self.root.preorder()definorder(self):print()if self.root isnotNone:print('Inorder: ') self.root.inorder()defpostorder(self):print()if self.root isnotNone:print('Postorder: ') self.root.postorder()defpprint(self,head_node=0,_pre="",_last=True,term=False): head_node = self.root if head_node ==0else head_node data ="*"if head_node isNoneelse head_node.dataprint(_pre, "`- "if _last else"|- ", data, sep="") _pre +=" "if _last else"| "if term:returnfor i, child inenumerate([head_node.leftChild, head_node.rightChild]): self.pprint(child, _pre, bool(i) ,term=not(bool(child)))if__name__=='__main__': tree =Tree() tree.insert(10) tree.insert(12) tree.insert(5) tree.insert(4) tree.insert(20) tree.insert(8) tree.insert(7) tree.insert(15) tree.insert(13) tree.pprint()print(tree.find(1))print(tree.find(12)) tree.preorder() tree.inorder() tree.postorder()