Binary Search Tree Operations (Search , Insert ,Delete ) with examples

•  Binary Search Tree Operations :-

1. 1)SEARCH OPERATION 

   • Search Operation is performed to search a particular element in the Binary Search Tree. 

2. 
   

 

• Rules: 

  1. For searching a given key in the BST, Compare the key with the value of root node. 
• • If the key is present at the root node, then return the root node. 

• • If the key is greater than the root node value, then recur for the root node’s right subtree. 
  • If the key is smaller than the root node value, then recur for the root node’s left subtree. 

 

2) INSERTION OPERATION 

        Insertion Operation is performed to insert an element in the Binary Search Tree. 

•  

• Rules: 

• -The insertion of a new key always takes place as the child of some leaf node. 

•  For finding out the suitable leaf node, 

• 1)Search the key to be inserted from the root node till some leaf node is reached. 

• 2)Once a leaf node is reached, insert the key as child of that leaf node. 

• 

  
  

  3)DELETION OPERATION 

  • Deletion Operation is performed to delete a particular element from the Binary Search Tree. 

   

  • When it comes to deleting a node from the binary search tree, following three cases are possible- 

     

  • Case-01: Deletion Of A Node Having No Child (Leaf Node)- 

  • Just remove / disconnect the leaf node that is to deleted from the tree. 

  
  

  • 

    
    
    

  • Case-02: Deletion Of A Node Having Only One Child- 

  • Just make the child of the deleting node, the child of its grandparent. 

  • 
    

• 

  
  

       Case-03: Deletion Of A Node Having Two Children- 

  • A node with two children may be deleted from the BST in the following two ways- 

     

  • Method 1: 

  • 1)Visit to the right subtree of the deleting node. 

  • 2)Pluck the least value element called as inorder successor. 

  • 3)Replace the deleting element with its inorder successor

  • 
    

  • 

    
          
    
    

  • Method 2: 

  • 1) Visit to the left subtree of the deleting node. 

     

  • 2) Pluck the greatest value element called as inorder predecessor. 

    • 
      

  • 3) Replace the deleting element with its inorder predecessor. 

     

  • 

    
    
    

•