How to insert a Node in a Binary Search Tree

Share

Recommended to visit before going through this article:
What is a Binary Search Tree? How to represent it ? And, related terminologies…

Inserting a node in a given Binary Search Tree is a process to add a new node; let’s say if node A has to be inserted then you got to follow below steps –

STEP 1: If there is no node in a given BST then insert node A as its Root Node.

STEP 2: Find the Node in a given Binary Search Tree where we need to insert A ( as either left or a right child ). To find so, just compare the value of node A with the root node’s value: 

if node A has a value greater than the root node’s value – traverse down the root node in its right node and Go to Step 2 by considering this right node as the root node (Note: if there is no right node straight go to Step 3)

if node A has a value lesser than the root node’s value – traverse down the root node in its left node and Go to Step 2 by considering this left node as the root node (Note: if there is no left node straight go to Step 3)

STEP 3: Once the Node is found using step 1:

if value of node A is greater than this Node’s value – insert A as the right child of this node
if value of node A is lesser than this Node’s value – insert A as the left child of this node

Above Algorithm can be implemented using two popular ways – Recursive and an Iterative way

BST,java


package org.gontuseries.bst;

public class BST {
          
    private Node root;

    public void insert(int value) {

        root = insert(value, root);
    }

    private Node insert(int value, Node currentNode) {

        if (currentNode == null) {
         return createNewNode(value);
        }

        if (value > currentNode.getValue()) { 
            currentNode = insert(value, currentNode.getRightNode()); 
        } else if (value < currentNode.getValue()) {
            currentNode = insert(value, currentNode.getLeftNode());
        } else {
            System.out.println("Node with the same value already 
                                                exists in the BST");
        }

     return currentNode;
    }

    private Node createNewNode(int value) {

        Node node = new Node(value);

     return node;
    }
}


package org.gontuseries.bst;

public class BST {

    private Node root;

    private void insert(int value) {

        if (root == null)
            root = createNewNode(value);
        else {
	    Node currentNode = root;
	    while (true) {

	        if (value > currentNode.getValue()) { 
                    if (currentNode.getRightNode() != null) { 
                        currentNode = currentNode.getRightNode();
                    } else { 
                        currentNode.setRightNode(createNewNode(value));
                    }
                } else if (value < currentNode.getValue()) {
        	    if (currentNode.getLeftNode() != null) {
	                currentNode = currentNode.getLeftNode();
		    } else {
		        currentNode.setLeftNode(createNewNode(value));
		    }
	        } else {
                    System.out.println("Node with the same value already
                                                exists in the BST");
	        }
          }
        }
    }

    private Node createNewNode(int value) {

        Node node = new Node(value);
	return node;
    }
}

Node.java


package org.gontuseries.bst;

public class Node {

    Node(int value) {
        this.value = value;
        this.leftNode = null;
        this.rightNode = null;
    }

    private int value;
    private Node leftNode;
    private Node rightNode;
    // --- writing all getters and setters for all properties 
    //i.e for value, leftNode, rightNode
}

Time Complexity: The run time complexity of insert operation using Recursive way is: O(height of a Binary Search Tree) i.e O(h) [worst-case]

a) In case of a  skewed Binary Search Tree the height is equal to the number of nodes in it; so, it becomes O(n)[worst-case]

b) In case of a Binary Search Tree built using some Tree Balancing Techniques like AVL, RED Black etc the height is equal to log (number of nodes in it); so it becomes log(n) [worst-case]

where, ‘n’ is the number of nodes in a binary search tree.