Binary Search Tree | Insertion

Binary Search Tree (BST) is node based binary tree data structure with the following properties:

• The Left subtree contains the nodes with keys less than the node's key.
• The Right subtree contains the nodes with keys greater than the node's key.
• Both the right and left subtree should also be binary search tree.
• There should not be any duplicate key.

Inserting a node in binary search tree behaves in the same manner as searching operation. Firstly, it checks whether the key is the same as that of root, if not then we either choose the right subtree or the left subtree depending on the value passed is greater or smaller than the root node value respectively.

Eventually, we will reach an external node where we will add the new node as its left or right child depending upon the node's key.

This is also a recursive operation, as we start from the root and go until we find the right place to insert to node.

Insertion time in a BST is proportional to the height of the tree.

Example

Insert: 5 2 8 1 4 7 9 0 3 6

                (5)

           /           \

         (2)            (8)

       /   \           /   \

    (1)    (4)        (7)  (9)

   /       /       /

 (0)     (3)    (6)

We used this structure with three members to represent each node in the tree. Here data represents the key of the node and lc and rc are pointers to the left and right subtree respectively

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

C Program

#include <stdio.h>
#include <stdlib.h>

typedef struct BST
{
   struct BST *lc,*rc;
   int data;
}BST;
 
void inOrder(BST *t)
{
    if(t != NULL) {
        inOrder(t->lc);
        printf("%d ",t->data);
        nOrder(t->rc);
    }
}
 
BST *insertNode(BST *T, int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found) {
        //Keeping track of the previous node...
        prev=curr; 
        // If item already exists...
        if(curr->data == item) {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item)
            curr = curr->lc;
        else
            curr = curr->rc;
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}
  
int main()
{
    BST *T = NULL;
    T = insertNode(T, 5);
    insertNode(T, 2);
    insertNode(T, 8);
    insertNode(T, 1);
    insertNode(T, 4);
    insertNode(T, 7);
    insertNode(T, 9);
    insertNode(T, 0);
    insertNode(T, 3);
    insertNode(T, 6);
    inOrder(T);
    return 0;
}

Output

0 1 2 3 4 5 6 7 8 9