JIYIK CN >

In the previous article Binary Search Tree , we discussed the recursive method to insert a node in BST. In this article, we will discuss the iterative method to insert a node in BST. It is better than the recursive method because the iterative insertion algorithm does not require additional space.

Binary Search Tree Iterative Insertion Algorithm

Assume rootthat is the root node of BST and keyis the element we want to insert.

• Create the node to be inserted - toinsert.
• Initialize two pointers, , currto point to root, and , prevto point to null. ( currTraverse the tree, prevkeeping track of it).
• When curr!= NULL, do the following.
  • Updated prevto currkeep track of it.
  • If curr->data> key, set currto curr->left, discarding the right subtree.
  • If curr->data< key, set currto curr->right, discarding the left subtree.
• If prev== NULL, the tree is empty. Create roota node.
• Otherwise if prev->data> key, then previnsert toinsert= to prev->leftthe left of toinsert.
• Otherwise if prev->data< key, then previnsert = on the right toinsertside prev->rightof toinsert.

BST Iterative Insertion Diagram

• First, we rootinitialize the BST by creating a node and insert it into it 5.
• 3is smaller than 5, so it is inserted 5to the left of .
• 4is smaller than 5, but 3larger than , so insert 3to the right of , but insert 4to the left of .
• 2is the smallest element in the current tree, so it is inserted at the leftmost position.
• 1is the smallest element in the current tree, so it is inserted at the leftmost position.
• 6is the largest element in the current tree, so it is inserted at the rightmost position.

This is how we insert elements inside a BST.

Iterative implementation of binary search tree insertion

#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);
}

Complexity of iterative insertion algorithm for binary search tree

Time Complexity

• Average situation

On average, the time complexity of inserting a node in a BST is comparable to the height of the binary search tree. On average, the height of a BST is O(logn). This happens when the formed BST is a balanced BST. Therefore, the time complexity is [Big Theta]: O(logn).

• Best Case

In the best case, the tree is a balanced BST. The time complexity of insertion in the best case is O(logn). It is the same as the time complexity in the average case.

• Worst case scenario

In the worst case, we may have to traverse from the root node to the deepest leaf node, which is the entire height of the tree h. If the tree is unbalanced, that is, it is skewed, the height of the tree may become n, so the worst-case time complexity of insertion and search operations is O(n).

Space complexity

The space complexity of the iterative insertion operation is O(1), since no additional space is required.