# Binary Search Tree Iterative Insert

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.

Binary Increment and Decrement Inst...
Binary Increment and Decrement Instructions - Omron PLC Programming

## BST Iterative Insert Algorithm

Let `root` be the root node of BST and `key` be the element we want to insert.

• ##### 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.

## BST Iterative Insert Illustration • ##### `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.

## Related Article - Data Structure

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion
• ## Related Article - Binary Tree

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion
• ## Related Article - Binary Search Tree

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• Linked List Deletion