Insert A Node In Binary Search Tree

Insert A Node In Binary Search Tree

In this post, you will learn how to insert a node in a binary search tree using inorder traversal.

 

To learn inserting a node in BST first you need to learn about recursion, which is a function calling itself.

#include<stdio.h>
#include<stdlib.h>
struct node{  

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

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

    return new;
} 
struct node *insert(struct node *root, int val){
    if(root==NULL)
        return newnode(val);
    if(root->key<val)
        root->right = insert(root->right,val);
    else if(root->key>val)
        root->left = insert(root->left, val);
    return root;
}
 
void inorder(struct node *root){
    if(root == NULL)
        return;
    inorder(root->left);
    printf("%d ",root->key);
    inorder(root->right);
}

    /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
 
int main(){
    struct node *root = NULL;
    root = insert(root,50);
    root = insert(root,30);
    root = insert(root,20);
    root = insert(root,40);
    root = insert(root,70);
    root = insert(root,60);
    root = insert(root,80);
    inorder(root);
    return 0;
}

In Inorder traversal we traverse from left-root-right.

 

Explanation

 

1. First, we are creating a function which will create a doubly linked list node in heap and return to the function which calling it. 
2. Now we will insert the node by calling the function insert in main and passing the value.
3. It will check if the root is Null then create a node.Since it is null so a node will be created. 
4. 50 will be inserted as the key.
5. After this again main function and 30 will be check if it is smaller than 50 so it will be inserted at the left side and points to null.
6. Similarly it will check for second value and so on.