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 toroot
andprev
pointing to null. (curr
traverses the tree andprev
maintain its trail). 
While
curr
!=NULL
, do the following: Update
prev
to becurr
to maintain its trail.  if
curr>data
>key
, setcurr
to becurr>left
, discard the right subtree.  if
curr>data
<key
, setcurr
to becurr>right
, discard the left subtree.
 Update

If
prev
==NULL
, it means that the tree is empty. Create theroot
node. 
Else if
prev>data
>key
then inserttoinsert
in the left ofprev
,prev>left
=toinsert
. 
Else if
prev>data
<key
then inserttoinsert
in the right ofprev
,prev>right
=toinsert
.
BST Iterative Insert Illustration

First, we initialize BST by creating a
root
node and insert5
in it. 
3
is smaller than5
so it gets inserted into the left of5
. 
4
is smaller than5
but large than3
, so it gets inserted into the right of3
but left of4
. 
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 averagecase, 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 bestcase occurs when the tree is a balanced BST. The bestcase time complexity of insertion is of the order of O(logn)
. It is the same as averagecase time complexity.
 WorstCase
In the worstcase, 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 worstcase 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.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion
 Linked List Merge Sort
Related Article  Binary Tree
 Convert Binary Tree to Binary Search Tree
 Binary Search Tree Check
 Binary Search Tree Inorder Succesor
 Binary Tree Traversal
 Binary Search Tree
 Binary Search Tree Delete