Binary Search Tree: Program to insert a node using iterative approach

Insert a node with a given data in a BST using the Iterative Approach.

For insertion, we use the BST Properties

All nodes to the left of the current node has lower data than the current node
All nodes to the right of the current node has greater data than the current node

Algorithm

1. If the root of the tree is null, then create a new node with data as dataToAdd and make the new node as root, and return from the algorithm.
2. Create a current variable and assign the root as a value to it
3. While the current is not null do:
   • If DataToAdd is less than the current data, then check left node of current:
     • If the left node of the current is null then assign the new node to the left, and return from the algorithm
     • Else change current to the current of left
   • Else check the right node of current:
     • If the right node of the current is null then assign the new node to the right, and return from the algorithm
     • Else change current to the current of right

Complexity

Average Case Time Complexity: O(LogN)
Worst Case Time Complexity: O(N)
Space Complexity: (1)

The Time Complexity heavily depends on the structure of the given tree,
if the given tree is balanced then the time complexity will be O(logN) and
for a skew tree the time complexity will be O(N), and
the Space Complexity is constant as we do not use extra space.

Java Code

 import java.util.ArrayDeque;
    import java.util.Queue;
     
    class BinarySearchTree {
     // Node class for Binary Search Tree
     class Node {
       int data;
       Node left, right;
     
       // Constructor to set the value of the node
       Node(int data) {
         this.data = data;
         this.left = null;
         this.right = null;
       }
     }
     
     private Node root = null;
     
     // Insert a value in BST Iteratively
     public void insert(int dataToAdd) {
       // Check if root is null,
       // if null then create a node and make it root
       if (root == null) {
         root = new Node(dataToAdd);
         return;
       }
     
       // Start traversing from the root and find the position of node to insert
       Node current = root;
       while (current != null) {
         // If the dataToAdd is less than the current data go to left else go to right
         if (dataToAdd < current.data) {
           // Insert the node if the position is empty
           if (current.left == null) {
             current.left = new Node(dataToAdd);
             return;
           }
           current = current.left;
         } else {
           if (current.right == null) {
             // Insert the node if the position is empty
             current.right = new Node(dataToAdd);
             return;
           }
           current = current.right;
         }
       }
     }
     
     // A function which prints the level order traversal representation of the BST
     public void printTree() {
       // Queue to store the current level of the binary tree
       Queue currentLevelQueue = new ArrayDeque();
       currentLevelQueue.offer(root); // Insert the root to the queue
     
       while (!currentLevelQueue.isEmpty()) {
         // Create a temporary queue to store the nodes of next level
         Queue tempQueue = new ArrayDeque();
         while (!currentLevelQueue.isEmpty()) {
           // Get the node from the queue and print it
           Node current = currentLevelQueue.poll();
           System.out.print(current.data + " ");
     
           // If current node has left then insert it to the tempQueue
           if (current.left != null) {
             tempQueue.offer(current.left);
           }
     
           // If current node has right then insert it to the tempQueue
           if (current.right != null) {
             tempQueue.offer(current.right);
           }
         }
         // Printing a new line at each level end
         System.out.println();
     
         // copy the contents of the tempQueue to the currentLevelQueue
         currentLevelQueue = tempQueue;
       }
     }
     
     public static void main(String[] args) {
       BinarySearchTree bst = new BinarySearchTree();
     
       // Inserting data in the binary tree
       bst.insert(8);
       bst.insert(2);
       bst.insert(6);
       bst.insert(12);
       bst.insert(11);
       bst.insert(10);
     
       System.out.println("Level wise Display after Insertion:");
       bst.printTree();
     }
     
  } 

Output

Level wise Display after Insertion:
8
2 12
6 11
10