# 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.

## 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).