# 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 – ## 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  ## 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 notstruct 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 Nodestruct 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 completevoid 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 followedstruct 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. • 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. • The next element, 13 , is compared to the root node. Since  15  > 13 it is inserted to the left of the root node. • 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. • 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. • 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. • 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. • 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. 