Insert A Node In Binary Search Tree In C

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.

How To Insert A Node In Binary Search Tree In C

#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. 

Pre order: 21 14 11 5 12 18 15 19 28 25 23 26 32 31 33



For more such posts, like this page and follow nkcoderz. Keep sharing our article with your friends.

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment