DSA Binary Search Tree

By | October 18, 2019
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.

Vamware

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)

Leave a Reply

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