How to Insert element into a BST (DSA) ?

Today we are going to learn about BST and how we can insert a single element or we can say single node into a BST**. It is easy for those who have already know about the BST and Double linked lists these to topics are important before you read this article . So i have provided the link for these topics you can refer it.-

1.For double linked list
2.For Binary tree

So before Knowing how to insert a single node into BST. You must have to know what BST is , BST is a

** Binary Search Tree**
which have some properties like :-

1. Left node have less value or as compare to root and right element
2. Root node have less value as compare to right node
3. And when we triverse the node by applying Inorder triversal it will give ascending sorted array.

It look like this

For inserting element into BST we need one pointer that point to root node because in some part we have to compare our key with root data that how we know wheather the key will going to insert either to left or right side .

So first we create a node and initilize it to behave as a BST.

This is the code which you can refer code is present in C language.

#include<stdio.h>
#include<stdlib.h>
struct node{
   struct node* left;
   int data;
   struct node* right;
};
struct node* createNode(int key){
   struct node * newNode = NULL;
   newNode = malloc(sizeof(struct node));
   newNode->left = NULL;
   newNode->data = key;
   newNode->right = NULL;

   return newNode;
}
void insertNewNode(struct node* root , int key){
    struct node * prev = NULL;
    while(root!=NULL){
        prev = root;
        if(key==root){
            printf("element cannot insert it is present 
                              inside the bst already");
            return ;
        }
        else if(key>root->data)
        {   
                root = root->right;
        }
        else{
            root = root->left;
        }
    }
    struct node * newNode = createNode(key);
    if(key>prev->data){
        prev->right = newNode;
    }
    else{
        prev->left = newNode;
    }
}
void inOrder(struct node* root){
     if(root == NULL){
        return root;
    }
    inOrder(root->left);
    printf("%d",root->data1`1);
    inOrder(root->right);

}
int main(){

    struct node* head1 = createBst(20);
    struct node* head2 = createBst(10);
    struct node* head3 = createBst(30);


    head1->left=head2;
    head1->right=head3;

    insertNewNode(head1,40);
    printf("%d\n",head1->right->right->data);
    inOrder(head1);




    return 0;
}

The above is the detailed content of How to Insert element into a BST (DSA) ?. For more information, please follow other related articles on the PHP Chinese website!