Binary Search Tree: Insertion

Insertion in a Binary Search Tree

Binary Search tree is fairly easy and we just need to know a few simple rules given below –

Insertion in a Binary Search Tree BST

Rules for Insertion in a Binary Search Tree (BST)

  • The left subtree for any given node will only contain nodes which are lesser than the current node
  • The right subtree for any given node will only contain nodes which are greater than the current node
  • Each subtree must also follow the above rules of BST

Pre Requisite to Insertion

So, first, we will learn how to search a given node(value), in a binary search tree

Insertion in a Binary Search Tree BST subtree 1

Searching in a Binary Search Tree

Let us say we want to 9 in the binary search tree given in our example above, what approach we would follow?

Algorithm

  • Start from the root node
  • Compare the value with the root node, if same then found, return True
  • If the value is less than the root node, recurse to the left node. Else recurse to the right node
  • Do this recursively, until the value is found or not found

Example

Assuming we want to find 9 in the above example

  1. The root node is 15, (9 <15) thus recursing to the left node
  2. Now, the left node is 13, (9<14) thus again, recursing to the left node
  3. Now, the left node is 8, (9>8) thus, recursing to the right node
  4. Finally, the right node is 9, (9=9), thus value found, return true

Code to implement Search

// A sample C function to check if a given node exists in a binary search tree or not
struct node* search(struct node* root, int value)
{
// Check if the root is null or value is present at root itself
if (root == NULL || root->value == value)
return root;

// Root is smaller than value, go to right subtree's node, doing recusion here
if (root->value < value)
return search(root->right, value);

// else only one case is left
// i.e. Root is greater than value, go to left subtree's node, doing recusion here
return search(root->left, value);
}

Insertion in a Binary Search Tree

Insertion is fairly simple if you understood search perfectly

  • Try to search the BST for the node to be inserted
  • As the node wouldn’t exist we will hit the leaf node, with null as child node right!
  • Insert the new node here
  • Voila! Party, you’ve inserted

Code for Binary Search Tree Insertion

// PrepInsta's program to do insertion in a Binary Search Tree (BST)
#include<stdio.h>
#include<stdlib.h>

// Basic struct of Tree
struct node
{
int val;
struct node *left, *right;
};

// Function to create a new Node
struct node* newNode(int item)
{
struct node* temp = (struct node *)malloc(sizeof(struct node));
temp->val = item;
temp->left = temp->right = NULL;
return temp;
}

// Function print the node in inorder format, when insertion is complete
void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->val);
inorder(root->right);
}
}

// Here we are finding where to insert the new node so BST is followed
struct node* insert(struct node* node, int val)
{
/* If the tree(subtree) is empty, return a new node by calling newNode func.*/
if (node == NULL) return newNode(val);

/* Else, we will do recursion down the tree to further subtrees */
if (val < node->val)
node->left = insert(node->left, val);
else if (val > node->val)
node->right = insert(node->right, val);

/* (Safety) return the node's pointer which is unchanged */
return node;
}

int main()
{
/* Our BST will look like this
100
/ \
40 140
/ \ / \
40 80 120 160 */
struct node* root = NULL;
root = insert(root, 100);
insert(root, 60);
insert(root, 40);
insert(root, 80);
insert(root, 140);
insert(root, 120);
insert(root, 160);


// Finally printing the tree using inorder
inorder(root);

return 0;
}

How it works?

  • In binary search trees, we use the INSERT function to add a new element in a tree.
  • Insertion is similar to searching wherein, we first check if the element is present in the given data or not. If not, the node is entered at that position.
  • If the data to be added is greater than the parent data node it is inserted towards the right of the parent; else it is inserted to the left of the parent.
  • In other words,
  • If  root > node, 

then the data node is added to the left sub-tree.

  • If  root < node, 

then the data node is added to the right sub-tree.

For Example: [15, 18, 13, 8, 14, 4, 16, 19, 9]

  • 15 being the first element becomes the root of the tree.
b1
  • The next element, 18, is now compared against the root node. Since  18 > 15 it is inserted to the right hand side of the root node.
b2
  • The next element, 13 , is compared to the root node. Since  15  > 13 it is inserted to the left of the root node.
b3
  • Now the next element 8  is compared to the root node. Since  8  < 15 it has to be inserted to the left subtree. Now again 8 is compared to 13 and since 8 <  13 it is added to the left of 13.
b4
  • The next element to be inserted is 14. Since 14 <  15 it will be added to the left subtree. Now again 14 is compared to 13  and since 14 > 13 it is added to the right of 13.
b5
  • The next element  to be inserted is 4. Since 4 < 15 it is to be added to the left subtree. Now again 4 compared to 13 and then it is compared to 8 and since 4 <  13 and 4 < 8 it is added to the left of 8.
s6
  • The next element to be inserted is 16. Since 16 > 15 it is to be added to the right subtree. Now again 16 is compared to 18 and since 16 < 18 it is added to the left of 18.
s7
  • The next element to be inserted is 19. Since 19 > 15 it is to be added to the right subtree. Now again 19 is compared to 18 and since 19 > 18 it is added to the right of 19.
  • The last element to be inserted is 9. Since 9 < 15 it is to be added to the left sub-tree. Now again 9 is compared to 13 and is then compared  8, and since 9 < 13 but  9  > 8 it is added to the right of 8.

 

s9