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 🙂 🙂

1. Teresa Georges says: