Implementing Binary Search Tree: Insertion

Binary Search Tree(BST) is a standard data structure which is very useful in case of searching because of O(log n) complexity in the worst case.

This post is the solution of the HackerRank challenge Binary Search Tree: Insertion.

Let us see the different implementations of the same problem. Please note these implementations are in java language.

Solution By Recursion:


static Node Insert(Node root,int value)
{
if(root == null) { //create a node and assign it when found the required node
   Node t = new Node();
   t.data = value;
   root = t;
}
else {
     if(root.data < value) {
root.right = Insert(root.right,value); //go to the right
} else if(root.data > value){
            root.left = Insert(root.left,value); //go to the left
     }
}

return root;
}

Time complexity: O(n)  Space Complexity: O(n) {because of recursive call}

In the worse case, A tree can be built only by left/right nodes, Thus a tree becoming a left-skew tree or a right-skew tree. Hence, We need to traverse all the nodes.

Same can be implemented in an iterative manner which will remove of recursive calls and will save the space complexity.

Solution By Iterative:


static Node Insert(Node root,int value)
 {
     Node t = new Node(); //create a node
     t.data = value;
     if(root == null){ //if it is an empty tree
          root = t;
     }
     else {
               Node p = root; //take the root node into temp variable so that root node can't be lost
               while(true){ //search for the correct position and then insert it
                      if(p.data > value){ //if value to be inserted is less then go left
                                if(p.left != null){//if left element is not null then it signifies that it has left node
                                         p = p.left;
                                }
                                else{  //found the node then insert and come out of loop.
                                        p.left = t;
                                        break;
                                 }
                       }
                       else if(p.data < value){
                                    if(p.right != null){
                                            p = p.right;
                                    }
                                    else{
                                             p.right = t;
                                             break;
                                    }
                        }
            }
      }

     return root;
 }

Time Complexity: O(n)    Space Complexity: O(1)

There can be multiple solutions to any problem. There can be better and simpler approach that one can come up. If there are any other alternatives that you know, do let me know via comment section.

Thanks for the reading. 🙂

Happy Coding 🙂 🙂

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.