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

Write a program to insert a node with a given data in a BST using the recursive 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

Inserting a node in a BST recursively requires two functions

• Used to pass the initial data to the Recursive Function
  • The Recursive callback function is called and the root and dataToAdd are passed to it as parameters
• The Main Recursive callback function will be used to compare and add a node with the data as dataToAdd,
  this is the main recursive function that implements the below algorithm

Algorithm

insertCallback(dataToAdd, node)

1. If the node is null, we got the position to insert the node, so create a new node with data equal to dataToAdd and return it
2. If dataToAdd is less than node data then:
   • Call the insertCallback with dataToAdd and left of the node as a parameter and
     store the value from the callback on the left of the node
3. Else:
   • Call the insertCallback with dataToAdd and right of the node as a parameter and
     store the value from the callback in the right of the node
4. Return node

In the Above Algorithm, the insertCallback is called inside the insert function by
passing dataToSearch and the root of the tree as the parameters.

Complexity

Average Case Time Complexity: O(LogN)
Worst Case Time Complexity: O(N)
Auxiliary Space Complexity: O(Height of Tree)

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)

Space Complexity is O(Height of Tree) because of the stack memory consumed by the recursive calls.

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 Recursively
     public void insert(int dataToAdd) {
       // Calling the callback function and passing root as parameter
       root = insertCallback(dataToAdd, root);
     }
     
     private Node insertCallback(int dataToAdd, Node node) {
       // If node is null then create the node with the dataToAdd and return it
       if (node == null) {
         return new Node(dataToAdd);
       }
     
       // Go to left or right depending on the dataToAdd value
       if (dataToAdd < node.data) {
         // The node from the insertCallback will be assigned to the left of node
         node.left = insertCallback(dataToAdd, node.left);
       } else {
         // The node from the insertCallback will be assigned to the right of node
         node.right = insertCallback(dataToAdd, node.right);
       }
     
       // Return the current node
       return node;
     }
     
     // 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();
       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