DSA Binary Search Tree

    A Binary Search Tree is a special Binary tree (each parent node can have maximum 2 node), which satisfy the following condition.

    • The tree must be a binary search tree.
    • The left sub-tree key value should be less than the parent node key value.
    • The right-sub tree key value should be greater than the parent node key value.

    If a tree satisfies the above 3 conditions then it would be considered as a Binary Search Tree.

    Binary Search Tree Representation

    Let’s represent a binary search tree which keys values are [31,16,61,8,23,46,77,19,28]

                            31
                           /  \
                          /    \
                         16     61
                        /   \   /  \
                       8    23  46  77
                            / \
                           19  29

    The binary tree is a Binary Search tree because each node has 2 or less than 2 child nodes, and each parent node left child is smaller than the parent node and the right child is greater than the parent node.

    Advantages of Binary Search Tree

    • It optimizes the searching algorithm, as we know that the elements on the right side are greater than the parent node and elements on the left side are smaller than the parent node so, with simple comparison, we can search any element efficiently.
    • The insertion of the new element in a binary search tree is also very easy.
    • If we compare it with the linked list and array it is more efficient.

    Complexities

    Algorithms Average Complexity Worst Complexity
    Space O(n) O(n)
    Search O(log n) O(n)
    Insert O(log n) O(n)
    Delete O(log n) O(n)

    Basic Operations on Binary Search Tree

    Like other data structure we can perform some basic operations on Binary Search Tree:

    • Insertion
    • Deletion
    • Traversal
    • Searching

    Insertion

    In BST the insertion takes place always at the bottom of a tree. No matter what the new element inserted in the tree become the leaf node of the tree. Suppose we have a tree:

                            31
                           /  \
                          /    \
                         16     61

    Insert

    100 is greater than root node 31 so it lay on the right subtree of the tree. But 31 already has a right child 61, so now we will compare the right child of the parent node with the new element 100.

                            31
                           /  \
                          /    \
                         16     61
    

    The right subtree has already a node 61 so we will compare 100 with 61, and 100 is greater than 61 so it resides as the right child of 61 because 61 does not have any child.

                            31
                           /  \
                          /    \
                         16     61
                                  \
                                  100

    Insertion algorithm

    def insert(key,data,currentnode):
        if not root:
            root = Node(key,data)
        else:
            if key < root.key:
                if currentnode.hasLeftChild():
                    insert(key,data,currentnode.leftchild)
                else:
                    currentnode.leftChild = Node(key,data)
            else:
                if currentnode.hasLeftChild():
                    insert(key,data,currentnode.leftchild)
                else:
                    currentnode.leftChild = Node(key,data)
    

    Deletion

    Deletion is the most complex and lengthy operation of BST, when we perform the deletion operation, we have to take care of three conditions.

    • The node we have to delete is a leaf node
    • The node we have to delete has only one child.
    • The node we have to delete has 2 child nodes.

    Traversal

    Like a binary tree, we can use any of the tree traversal methods on BST to visits each node. Those three methods are

    • Pre-Order Traversal
    • In-Order Traversal
    • Post-Order Traversal.

    Searching

    To retrieve the data of any particular node we can perform the search operation on the Binary search tree. To search the data, we use the corresponding key value.

    Implementation of Binary Search Tree

    In Python

    Here we will use python to implement a Binary Search Tree. We use the class to create the structure for binary search tree and use node to create specific nodes that will reside in the BST.

    class Node:
        def __init__(self,key,val,left=None,right=None,parent=None):
            self.key = key
            self.data = val
            self.leftChild = left
            self.rightChild = right
            self.parent = parent
        def hasLeftChild(self):
            return self.leftChild
        def hasRightChild(self):
            return self.rightChild
        def isLeftChild(self):
            return self.parent and self.parent.leftChild == self
        def isRightChild(self):
            return self.parent and self.parent.rightChild == self
        def isRoot(self):
            return not self.parent
        def isLeaf(self):
            return not (self.rightChild or self.leftChild)
        def hasAnyChildren(self):
            return self.rightChild or self.leftChild
        def hasBothChildren(self):
            return self.rightChild and self.leftChild
        def replaceNodeData(self,key,value,lc,rc):
            self.key = key
            self.data = value
            self.leftChild = lc
            self.rightChild = rc
            if self.hasLeftChild():
                self.leftChild.parent = self
            if self.hasRightChild():
                self.rightChild.parent = self
    class BinarySearchTree:
    
        def __init__(self):
            self.root = None
            self.size = 0
    
        def length(self):
            return self.size
    
        def __len__(self):
            return self.size
    
        def insert(self,key,val):
            if self.root:
                self._insert(key,val,self.root)
            else:
                self.root = Node(key,val)
            self.size = self.size + 1
    
        def _insert(self,key,val,currentNode):
            if key < currentNode.key:
                if currentNode.hasLeftChild():
                       self._insert(key,val,currentNode.leftChild)
                else:
                       currentNode.leftChild = Node(key,val,parent=currentNode)
            else:
                if currentNode.hasRightChild():
                       self._insert(key,val,currentNode.rightChild)
                else:
                       currentNode.rightChild = Node(key,val,parent=currentNode)
    
        def __setitem__(self,k,v):
            self.insert(k,v)
    
        def search(self,key):
            if self.root:
                res = self._search(key,self.root)
    
                if res:          
                    return res.data
                else:
                    return None
            else:
                return None
    
        def _search(self,key,currentNode):   
            if not currentNode:
                return None
            elif currentNode.key == key:
                return currentNode
            elif key < currentNode.key:
                return self._search(key,currentNode.leftChild)
            else:
                return self._search(key,currentNode.rightChild)
    
        def __searchitem__(self,key):
            return self.search(key)
    
        def __contains__(self,key):
            if self._search(key,self.root):
                return True
            else:
                return False
    
        def delete(self,key):     
            if self.size > 1:          
                nodeToRemove = self._search(key,self.root)
                if nodeToRemove:
                    self.remove(nodeToRemove)
                    self.size = self.size-1
                else:
                    raise KeyError('Error, key not in tree')
            elif self.size == 1 and self.root.key == key:
                self.root = None
                self.size = self.size - 1
            else:
                raise KeyError('Error, key not in tree')
    
        def __delitem__(self,key):   
            self.delete(key)
    
        def spliceOut(self):
            if self.isLeaf():
                if self.isLeftChild():             
                    self.parent.leftChild = None
                else:
                    self.parent.rightChild = None
    
            elif self.hasAnyChildren():
                if self.hasLeftChild():
                    if self.isLeftChild():
                        self.parent.leftChild = self.leftChild
                    else:
                        self.parent.rightChild = self.leftChild
                        self.leftChild.parent = self.parent
    
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                    self.rightChild.parent = self.parent
    
    
        def findSuccessor(self):  
            succ = None
            if self.hasRightChild():
                succ = self.rightChild.findMin()
            else:
                if self.parent:
                    if self.isLeftChild():            
                        succ = self.parent
                    else:
                        self.parent.rightChild = None
                        succ = self.parent.findSuccessor()
                        self.parent.rightChild = self
            return succ
    
        def findMin(self):
    
            current = self
            while current.hasLeftChild():
                current = current.leftChild
            return current
    
        def remove(self,currentNode):
            if currentNode.isLeaf(): #leaf
                if currentNode == currentNode.parent.leftChild:
                    currentNode.parent.leftChild = None
                else:
                    currentNode.parent.rightChild = None
            elif currentNode.hasBothChildren(): #interior
                succ = currentNode.findSuccessor()
                succ.spliceOut()
                currentNode.key = succ.key
                currentNode.data = succ.data
            else: # this node has one child
                if currentNode.hasLeftChild():
                    if currentNode.isLeftChild():
                        currentNode.leftChild.parent = currentNode.parent
                        currentNode.parent.leftChild = currentNode.leftChild
                    elif currentNode.isRightChild():
                        currentNode.leftChild.parent = currentNode.parent
                        currentNode.parent.rightChild = currentNode.leftChild
    
                    else:
                        currentNode.replaceNodeData(currentNode.leftChild.key,
                                        currentNode.leftChild.data,
                                        currentNode.leftChild.leftChild,
                                        currentNode.leftChild.rightChild)
                else:
             
                    if currentNode.isLeftChild():
                        currentNode.rightChild.parent = currentNode.parent
                        currentNode.parent.leftChild = currentNode.rightChild
                    elif currentNode.isRightChild():
                        currentNode.rightChild.parent = currentNode.parent
                        currentNode.parent.rightChild = currentNode.rightChild
                    else:
                        currentNode.replaceNodeData(currentNode.rightChild.key,
                                        currentNode.rightChild.data,
                                        currentNode.rightChild.leftChild,
                                        currentNode.rightChild.rightChild)

    People are also reading: