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?
- 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
Assuming we want to find 9 in the above example
- The root node is 15, (9 <15) thus recursing to the left node
- Now, the left node is 13, (9<14) thus again, recursing to the left node
- Now, the left node is 8, (9>8) thus, recursing to the right node
- 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)
// 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)
// Basic struct of Tree
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;
// Function print the node in inorder format, when insertion is complete
void inorder(struct node* root)
if (root != NULL)
printf("%d \n", root->val);
// 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 */
/* Our BST will look like this
/ \ / \
40 80 120 160 */
struct node* root = NULL;
root = insert(root, 100);
// Finally printing the tree using inorder
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.