Insertion in Binary Search Tree
- If you know search operation then it's easy
- And as there are no duplicates in a binary search tree. So, if you search the element you are being asked to insert, you would print that the number already exists.
Here is an example binary search tree, and the element we want to insert is 9.
- Start from the root node, and check if the element you want to insert is greater than or lesser than.
- Since 9 is greater than 8
- move to the right of the root
- now root is the 10
- since this time 9 is less then 10
- move to the left of element 10
- since there are no elements to its left
- insert 9 there.
This was one simple case, but things becomes more complex when you have to insert your element at some internal position and not at the leaf.
- Before you insert a node, the first thing you would do is to create that node and allocate memory to it in heap using malloc or createNode function.
- Initialize the node with the data given, and both the righ and the left member of the node should be marked NULL.
- Another important thing to see here is the pointer you would follow the correct position with.
- In above example, to be able to insert at that position, the pointer must be at node 10.
- And then you check wheter going to the left side is good, or the right.
- Here, you came to the left, but had it been right, we would have updated our pointer ptr further and maintained a second pointer to the previous root.
Creating the insert function
- Create a void function insert and pass the pointer to the root node, and the data of the node you want to insert as its parameter
- Use two struct pointers to traverse through the tree.
- One of them would be our root which we would traverse through the nodes.
- Another one would be prev which stores the pointer to the previous root
- Run a while loop that is for until we reach some leaf, and couldn't traverse further.
- So, run thant loop until the root becomes NULL
- Inside that loop
- make the prev = current loop. Since we would definitely move further because this root is not a NULL.
- check, if the root itself is not equal to the node we are trying to insert. That
is,
- Write an if condition to see if there are any duplicates here
- If there is return from the function here itself.
- move either to the left of this root or to the right of this root.
- Further in the loop, check if the element you want to insert is less than the
current root.
- If it is, update the root to the left element of the struct root.
- If it isn't, update the root tot the right elment of the struct root.
- And since we have already stored this root in the prev node, there ins't any issure updating.
- And finally, you will have a prev node as the outcome at the end after this loop finishes.
- Now, the only procefure left now is to link these nodes together, that it the prev node, the new node and the node next to the prev.
- Now before you insert, make sure you create that new struct node.
void insert(struct node *root, int key){
struct node *prev = NULL;
while(root!=NULL){
prev = root;
if(key==root->data){
printf("Cannot insert %d, already in BST", key);
return;
}
else if(key<root->data){
root = root->left;
}
else{
root = root->right;
}
}
struct node* new = createNode(key);
if(key<prev->data){
prev->left = new;
}
else{
prev->right = new;
}
}
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(int data){
struct node *n; // creating a node pointer
n = (struct node *) malloc(sizeof(struct node)); // Allocating memory in the heap
n->data = data; // Setting the data
n->left = NULL; // Setting the left and right children to NULL
n->right = NULL; // Setting the left and right children to NULL
return n; // Finally returning the created node
}
void insert(struct node *root, int key){
struct node *prev = NULL;
while(root!=NULL){
prev = root;
if(key==root->data){
printf("Cannot insert %d, already in BST", key);
return;
}
else if(key<root->data){
root = root->left;
}
else{
root = root->right;
}
}
struct node* new = createNode(key);
if(key<prev->data){
prev->left = new;
}
else{
prev->right = new;
}
}
int main(){
// Constructing the root node - Using Function (Recommended)
struct node *p = createNode(5);
struct node *p1 = createNode(3);
struct node *p2 = createNode(6);
struct node *p3 = createNode(1);
struct node *p4 = createNode(4);
// Finally The tree looks like this:
// 5
// / \
// 3 6
// / \
// 1 4
// Linking the root node with left and right children
p->left = p1;
p->right = p2;
p1->left = p3;
p1->right = p4;
insert(p, 16);
printf("%d", p->right->right->data);
return 0;
}
