Insertion in a Binary Search Tree

A Binary Search Tree is a Tree in which each node has not more than two child nodes, and each of the child nodes are inserted in the tree based on a certain rule - the left child should have value less than the parent node and the right child should have the value greater than the parent node.

A good example for a Binary Search Tree can be seen in the image below - Now as you can see:

1. 21 is the first element to be inserted. As the tree is empty, 21 becomes the root node.

2. 28 is the second element to be inserted. As we know that 28 > 21, 28 becomes the right child node of 21 (as right child should have value greater than the parent node).

3. 14 is the next value to be inserted. As 14 < 21, we insert it as the left child node of 21( as left child should have value less than the parent node).

4. Next up, 32 is inserted. As 32 > 21, we know that it can be inserted in the right subtree of 21. But, right child of 21 already exists. So, in this case, what we do is - reach the right child of 21 and check if 32 is greater than it or not. So here, the steps that we can follow are -

   1. Go to the root node (here, root node = 21).
   2. Compare the value with the root node (32 < 21)
   3. But as the right child of root node already exists, we move to the right child of root node(28 here).
   4. Compare the value (32 > 28).
   5. As the node to be inserted is greater than the node and the right child spot is vacant for this node, we insert the new node here.

And so on and so forth.

Insertion in Binary Search Tree

A generalised method of insertion of nodes in the binary tree can be described something like this -

1. Always start with the root node.
2. Compare the values with root node.
3. If the value is less than the root node, first check if the left child of root node is empty or not - 1. If it is empty, insert the new node there. 2. If not, move downwards in the tree, compare the values and check for empty spot repeatedly until you find it, and then insert the node there.
4. If the value is greater than the root node, first check if the right child node is empty or not - 1. If empty, insert the new node there. 2. If not, move downwards in the tree, compare the values and check for empty spot repeatedly until you find it, and then insert the node there.

Code for insertion

The implementation of the same method looks something like this in C :

NODE *insertInTree(int val, NODE *root){
    NODE *newnode = createnode(val);
    if(root  == NULL){
        root = newnode;
    }else{
        //compare the value
        if(newnode->data <= root->data){ // newnode data less than or equal to root node data
            //insertion to the left
            if(root->left == NULL){//check if the spot is empty
                root->left = newnode;
            }else{//if not empty
                return insertInTree(val, root->left); //goes downwards to the left subtree
                //compares the value and checks for empty spot
            }
        }
        else if(newnode->data > root->data){//newnode has value greater than root node.
        //insertion to the right
            if(root->right == NULL){//check if empty
                root->right = newnode;
            }
            else{// if not empty
                return insertInTree(val, root->right); // goes downwards to the right subtree
                //compares the value and checks for empty spot.
            }
        }
    }
    return root;
}

So, summing the above code up, we just recursively call the insert function based on the result of comparison of values until we find an empty spot in the tree and then we finally insert the node.

This is it.

I hope you enjoyed reading this article and got a clear idea of the concept. You can find more such articles here.

Thanks for reading!