# Binary Search Tree Iterative Insert

- BST Iterative Insert Algorithm
- BST Iterative Insert Illustration
- BST Iterative Insert Implementation
- BST Iterative Insert Algorithm Complexity

In the previous article Binary Search Tree, we discussed the recursive approach to insert a node in BST. In this post, we will discuss the iterative approach to insert a node in BST. It is better than the recursive method as no extra space is required by the iterative insertion algorithm.

## BST Iterative Insert Algorithm

Let `root`

be the root node of BST and `key`

be the element we want to insert.

##### Create the node to be inserted -

`toinsert`

.##### Initialize two pointers,

`curr`

pointing to`root`

and`prev`

pointing to null. (`curr`

traverses the tree and`prev`

maintain its trail).##### While

`curr`

!=`NULL`

, do the following:- Update
`prev`

to be`curr`

to maintain its trail. - if
`curr->data`

>`key`

, set`curr`

to be`curr->left`

, discard the right subtree. - if
`curr->data`

<`key`

, set`curr`

to be`curr->right`

, discard the left subtree.

- Update
##### If

`prev`

==`NULL`

, it means that the tree is empty. Create the`root`

node.##### Else if

`prev->data`

>`key`

then insert`toinsert`

in the left of`prev`

,`prev->left`

=`toinsert`

.##### Else if

`prev->data`

<`key`

then insert`toinsert`

in the right of`prev`

,`prev->right`

=`toinsert`

.

## BST Iterative Insert Illustration

##### First, we initialize BST by creating a

`root`

node and insert`5`

in it.`3`

is smaller than`5`

so it gets inserted into the left of`5`

.`4`

is smaller than`5`

but large than`3`

, so it gets inserted into the right of`3`

but left of`4`

.`2`

is the smallest element in the current tree, so it gets inserted at the leftmost position.`1`

is the smallest element in the current tree, so it gets inserted at the leftmost position.`6`

is the largest element in the current tree, so it gets inserted at the rightmost position.

This is how we insert elements inside a BST.

## BST Iterative Insert Implementation

```
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node *newNode(int item) {
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
void insert(Node* &root, int key)
{
Node* toinsert = newNode(key);
Node* curr = root;
Node* prev = NULL;
while (curr != NULL) {
prev = curr;
if (key < curr->key)
curr = curr->left;
else
curr = curr->right;
}
if (prev == NULL) {
prev = toinsert;
root = prev;
}
else if (key < prev->key)
prev->left = toinsert;
else
prev->right = toinsert;
}
int main() {
Node *root = NULL;
insert(root, 5);
insert(root, 3);
insert(root, 8);
insert(root, 6);
insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 7);
inorder(root);
}
```

## BST Iterative Insert Algorithm Complexity

### Time Complexity

- Average Case

On average-case, the time complexity of inserting a node in a BST is of the order of height of binary search tree. On average, the height of a BST is `O(logn)`

. It occurs when the BST formed is a balanced BST. Hence the time complexity is of the order of [Big Theta]: `O(logn)`

.

- Best Case

The best-case occurs when the tree is a balanced BST. The best-case time complexity of insertion is of the order of `O(logn)`

. It is the same as average-case time complexity.

- Worst-Case

In the worst-case, we might have to traverse from root to the deepest leaf node, i.e., the whole height `h`

of the tree. If the tree is unbalanced, i.e., it is skewed, the tree’s height may become `n`

, and hence the worst-case time complexity of both insert and search operation is `O(n)`

.

### Space Complexity

The iterative insert operation’s space complexity is `O(1)`

because no extra space is required.