inserting a node in a binary search tree

Given a binary search node and a value, insert the new node into the BST in the correct place.

Example

Insert data into BST


Algorithm

1. Create a new BST node and assign values to it.

2. insert(node, key)

     i) If root == NULL,

         return the new node to the calling function.

     ii) if root=>data < key

         call the insert function with root=>right and assign the return value in root=>right.

        root->right = insert(root=>right,key)

     iii) if root=>data > key

         call the insert function with root->left and assign the return value in root=>left.

         root=>left = insert(root=>left,key)

3. Finally, return the original root pointer to the calling function.



Binary search tree insertion code


struct node *insert(struct node *root, int val)
{
    /*
     * It will handle two cases,
     * 1. if the tree is empty, return new node in the root
     * 2. if the tree traversal reaches NULL, it will return the new node
     */
    if(root == NULL)
        return getNewNode(val);
    /*
     * if given val is greater than root->key,
     * we should find the correct place in the right subtree and insert the new node
     */
    if(root->key < val)
        root->right = insert(root->right,val);
    /*
     * if given val is smallar than root->key,
     * we should find the correct place in the left subtree and insert the new node
     */
    else if(root->key > val)
        root->left = insert(root->left,val);
    /*
     * It will handle two cases
     * (Prevent the duplicate nodes in the tree)
     * 1.if root->key == val it will straight away return the address of the root node
     * 2.After the insertion, it will return the original unchanged root's address
     */
    return root;
}



The getNewNode function

This function allocates and returns the new node with the given data and the left and right pointer as NULL.


struct node *getNewNode(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->key   = val;
    newNode->left  = NULL;
    newNode->right = NULL;

    return newNode;
}



Visual Representation of binary search tree insertion algorithm

Follow the step numbers(given in the circle) to understand the code flow correctly.

Try to draw the diagram by yourself for better understanding.

1. insert 100

BST insert 100

Diagram Explanation

1. Main Function

root = NULL. address of root = 4444. And the main function calling the insert function with root and an element 100. root = insert(root, 100);

2. Insert Function

The insert function receives root (NULL) and an element 100.

Since root == NULL, the first if statement will take control. i.e.

if(root == NULL)
    return getNewNode(val);

It will call the getNewNode function with an element 100.

3. getNewNode() function creates a new node with the given value. Let's assume that the new node's address as 1024. Then 1024 will be returned to the insert function.

4. Insert function returns the received new node's address(1024) to the main function. Now root will receive the new node's address 1024.

5. Finally, the new BST.

2. insert 50

BST insert 50

1. insert 150

BST insert 150


implementation of Binary Search Tree Insertion

/*
 * Program  : Binary Search Tree insertion
 * Language : C
 */

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

struct node
{
    int key;
    struct node *left;
    struct node *right;
};

//this function will return the new node with the given value
struct node *getNewNode(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->key   = val;
    newNode->left  = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node *insert(struct node *root, int val)
{
    /*
     * It will handle two cases,
     * 1. if the tree is empty, return new node in root
     * 2. if the tree traversal reaches NULL, it will return the new node
     */
    if(root == NULL)
        return getNewNode(val);
    /*
     * if given val is greater than root->key,
     * we should find the correct place in right subtree and insert the new node
     */
    if(root->key < val)
        root->right = insert(root->right,val);
    /*
     * if given val is smallar than root->key,
     * we should find the correct place in left subtree and insert the new node
     */
    else if(root->key > val)
        root->left = insert(root->left,val);
    /*
     * It will handle two cases
     * (Prevent the duplicate nodes in the tree)
     * 1.if root->key == val it will straight away return the address of the root node
     * 2.After the insertion, it will return the original unchanged root's address
     */
    return root;
}

/*
 * it will print the tree in ascending order
 * we will discuss about it in the upcoming tutorials
 */
void inorder(struct node *root)
{
    if(root == NULL)
        return;
    inorder(root->left);
    printf("%d ",root->key);
    inorder(root->right);
}

int main()
{
    struct node *root = NULL;
    root = insert(root,100);
    root = insert(root,50);
    root = insert(root,150);
    root = insert(root,50);

    inorder(root);

    return 0;
}