1.
Introduction
2.
What is insertion in BST?
3.
How to Insert a value in a Binary Search Tree
4.
Method 1: Iterative method
4.1.
Algorithm
4.2.
Implementation in C
4.3.
Complexity Analysis
5.
Method 2: Recursive method
5.1.
Algorithm
5.2.
Implementation in C
5.3.
Complexity Analysis
6.
6.1.
What is a Binary Tree?
6.2.
How do you insert a value in a BST?
6.3.
What is insertion and deletion in BST?
6.4.
Can we insert duplicates in BST?
6.5.
Where do insertions happen in a binary search tree?
7.
Conclusion
Last Updated: May 29, 2024
Easy

# Insertion in Binary Search Tree(BST)

Malay Gain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

Binary search tree BST is one type of binary tree Data Structure that is either empty, or each node in the tree contains a key and:

(i) all keys in the left subtree of T are less (numerically or alphabetically) than the key  in the root node of T;

(ii) all keys in the right subtree of T are greater than the key in the root node of the BST;

(iii) the left and right subtrees of the BST are also binary search trees.

While inserting nodes in a binary search tree, we should be conscious that it should not violate the property of a binary search tree after insertion.

## What is insertion in BST?

Insertion in a Binary Search Tree (BST) is the process of adding a new node into the tree while maintaining the BST property. The new node's value is compared with existing nodes, and it is placed as a child of an appropriate parent node based on whether it is smaller or larger. This ensures that the left subtree of any node contains only smaller values, and the right subtree contains only larger values, preserving the ordered structure of the BST.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## How to Insert a value in a Binary Search Tree

Below are the steps to insert a value into a Binary Search Tree (BST):

1. Start at the Root: Begin at the top of the tree, the root

2. Compare Values: Compare the value you want to insert with the current node's value

3. Go Left or Right: If it's smaller, move to the left else if it's larger, then move to the right

4. Repeat Comparison: Keep comparing and moving left or right until you find a spot where you can't go further because there's no more left or right child

5. Insert the Node: Create a new node with the value to be inserted

## Method 1: Iterative method

### Algorithm

• For inserting in the Binary Tree, the value is compared with that of the root.
• If the given value is lesser than the rootâ€™s, then move to rootâ€™s left, and it is compared with rootâ€™s left child value.
• If the given value is greater than the rootâ€™s, then move to rootâ€™s right, and it is compared with rootâ€™s right child value.
• This comparison continues until a leaf node is reached.
• Then new node is inserted as a left or right child of the leaf node depending on its value.
• For empty BST, the value is directly inserted as the rootâ€™s key.

### Implementation in C

``````#include<bits/stdc++.h>
using namespace std;
/************* BST node ************/
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/************* insertion function************/
TreeNode* insertIntoBST(TreeNode* root, int val) {

TreeNode* curr=root,*node=new TreeNode(val);
while(curr){

// curr val greater than val ,new node will be in left subtree

if(curr->val > val){
if(curr->left){
curr=curr->left;
}else{
curr->left=node;
break;
}

//curr val less than Val, the new node will be in the right subtree
}else{

if(curr->right){
curr=curr->right;
}
else{
curr->right=node;
break;
}
}
}
return root?root:node;
}

/**** function to perform inorder traversal on the BST  ***/
void inorder(TreeNode* root)
{
if (root == nullptr) {
return;
}

inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}

int main()
{
int keys[] = {4,2,7,1,3,5};

TreeNode* root = nullptr;
for (int key: keys) {
root = insertIntoBST(root, key);
}

inorder(root);

return 0;
}``````

### Complexity Analysis

Time complexity: For the above solution, the time complexity is O(h), where h is the height of the binary search tree. In the worst-case height becomes equal to the number of nodes in the BST(skewed tree).

Space complexity: O(1)

## Method 2: Recursive method

### Algorithm

• (Base Condition) Examine the root if it is null, create BST node with given value and return the node pointer
• If the given value is lesser than the rootâ€™s, recursively insert the new node to the left subtree.
• If the given value is greater than the rootâ€™s, recursively insert the new node to the right subtree.

### Implementation in C

``````#include<bits/stdc++.h>
using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/************* insertion function************/

TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root){
TreeNode* newNode=new TreeNode(val);
return newNode;
}

//root val greater than val ,  the new node will be in the left subtree
if(root->val > val){

root->left=insertIntoBST(root->left,val);

}

//root val lesser than val, the new node will be in the right subtree
else{
root->right=insertIntoBST(root->right,val);

}
return root;
}

/** function to perform inorder traversal on the BST **/
void inorder(TreeNode* root)
{
if (root == nullptr) {
return;
}

inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}

int main()
{
int keys[] = {4,2,7,1,3,5};

TreeNode* root = nullptr;
for (int key: keys) {
root = insertIntoBST(root, key);
}

inorder(root);

return 0;
}``````

output :1 2 3 4 5  7

### Complexity Analysis

Time complexity: For the above solution, the time complexity is O(h), where h is the height of the binary search tree. In the worst-case, height becomes equal to the number of nodes in the BST(skewed tree).

Space complexity: Due to stack space for recursive calls, space complexity is O(h) at the worst case.

### What is a Binary Tree?

A tree is called a binary tree if every node has at most two children nodes.  A binary tree node constitutes a left pointer, a right pointer, and a data element. An empty binary tree (with zero nodes) is also a valid binary tree.

### How do you insert a value in a BST?

In order to insert a value in BST, we compare the value with nodes, going left if smaller and right if larger. Inserting at a leaf node while maintaining the BST property.

### What is insertion and deletion in BST?

Insertion in BST means to add a value while preserving order, and deletion in BST refers to removing a node while maintaining the BST structure.

### Can we insert duplicates in BST?

In a standard BST, duplicate values are usually not allowed. Insertion may be ignored or handled differently based on implementation.

### Where do insertions happen in a binary search tree?

Insertions in a Binary Search Tree or BST occur at leaf nodes or null positions in the tree. When inserting a new node, the BST is traversed from the root node to find the appropriate position for the new node.

## Conclusion

This article covered different methods of how to make insertion in the Binary Search Tree. We have learned about the various algorithms to insert nodes in BSTs, but thatâ€™s not enough for us.

Side by side, we should also learn about searching and deletion operations in  Binary Search Tree.