Binary Search Tree Iterative Insert

  1. BST Iterative Insert Algorithm
  2. BST Iterative Insert Illustration
  3. BST Iterative Insert Implementation
  4. 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.
  • 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

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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Data Structure

  • Binary Tree Traversal
  • Linked List
  • Related Article - Binary Tree

  • Convert Binary Tree to Binary Search Tree
  • Binary Search Tree
  • Related Article - Binary Search Tree

  • Linked List Reversal
  • Binary Search Tree Check