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

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

**Start at the Root:** Begin at the top of the tree, the root

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

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

**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

**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)

You can also read about __insertion into bst__.

**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.

**Frequently Asked Questions**

**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.

Recommended Reading:

**Recommended problems -**

After you've mastered insertion, you should learn how to delete a node in BST. Check out the video below, which covers both the insertion and deletion of a node in BST