Insertion In Binary Search Tree In Java

Insertion In Binary Search Tree

Binary Search Tree is a rooted binary tree whose internal nodes each a key greater than all the keys in the node’s left subtree and less than those in it’s right subtree. Insertion function is used to add new element in a binary search tree at appropriate position. In this article we will perfom insertion in binary search tree using recursion in java.

Insertion in Binary Search Tree

Example To Insert A Node In Binary Search Tree

Example of insertion in Binary Search Tree

Algorithm To Insert In BST

Algorithm(ROOT, ITEM):
  1. If ROOT is null , Allocate the memory for ROOT.Set the ITEM to value and left and right pointer of ROOT , point to null.
  2. Check if the ITEM is less than the root element of the tree , if it is true then recursively perform this operation to the left of the tree.
  3. Else if the ITEM is greater than the root , then recursively perform this operation for the right of the tree.
  4. Insert a node where null is encountered.
  5. Return the  ROOT of the tree.

CODE FOR INSERTION IN BST

import java.util.*;

/*class Representing a Node of a tree */
class Node
{
   int value;
   Node left,right;
   Node(int value)
   {
       this.value=value;
       left=right=null;
   }
}
class Insertion
{
   Node root; //root of the tree
   //Constructor to intialize root with null
   Insertion()
   {
       root=null;
   }
   //preorder Traversal of binary tree
   public static void preorder(Node ptr)
   {
       if(ptr==null)
       return ;
       System.out.print(ptr.value+" ");
       preorder(ptr.left);
       preorder(ptr.right);
    }
   public void insert(int item)
   {
       root =insertNode(root,item); //calling inserNode() method
   }
   public Node insertNode(Node root,int item)
   {
       if(root==null)     //if root is null create a new Node
       {
           root=new Node(item);
           return root;
        }
       if(item<root.value)  //if item is less than the current value then traverse left subtree
           root.left= insertNode(root.left,item);
           else if(item>root.value) //if item is greater than the cureent value then traverse the right subtree
           root.right=insertNode(root.right,item);
           return root;
   }
   public static void main(String[] args)
   {
       Insertion tree=new Insertion();
       /*inserting node one by one in Binary Search Tree */
       tree.insert(30);
       tree.insert(50);
       tree.insert(55);
       tree.insert(45);
       tree.insert(10);
       tree.insert(5);
       tree.insert(15);
       tree.insert(12);
       //print preorder traversal of binary tree
       tree.preorder(tree.root);
   }
}

Output:

30 10 5 15 12 50 45 55

Time Complexity:

The worst-case time complexity of search and insert operations is O(h) where h is the height of the Binary Search Tree. In the worst case, we may have to    travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become    O(n).