How to insert an element into a BST (DSA) ?

Today we will learn bst and how to insert a single element (or we can say a single node) into a bst**. This is easy for those who already know bst and double-linked lists, and these topics are important before reading this article. So I provided links to these topics, you can refer to it. -

1. For double-linked tables
2. For binary trees

So before you understand how to insert a single node into bst. You must know what bst is, bst is a

** Binary search tree**
It has some properties, such as :-

1. The value of the left node is smaller or compared to the root and right elements
2. The root node has a smaller value than the right node
3. When we triple the node through the in-order tritree application, it will give an ascending array.

Looks like this

In order to insert the element into bst, we need a pointer to the root node, because in some parts we have to compare the key to the root data so that we know whether the key will be inserted to the left or right.

First we create a node and initialize it to bst.

This is the code you can refer to, the code is implemented 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;
}
</stdlib.h></stdio.h>

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