Search⌘ K
AI Features

Insertion in BST (Complete Implementation)

Explore the iterative and recursive techniques to insert nodes in a Binary Search Tree. Understand how to navigate the tree, create new nodes, and analyze the time complexity for both approaches.

Introduction

There are two techniques to code an Insertion Function:

  • Iterative
  • Recursive

First, let’s see how Iterative methodology works. The following tree is what we will build once we successfully implement the insertion functionality in Binary Search Tree code.

%0 6 6 8 9 6->8 4 4 6->4 7 8 8->7 12 12 8->12 5 5 4->5 3 2 4->3 10 10 12->10 14 14 12->14

Insertion Implementation (Iterative)

Java
class binarySearchTree {
private Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
//Iterative Function to insert a value in BST
public boolean add(int value) {
//If Tree is empty then insert Root with the given value inside Tree
if (isEmpty()) {
root = new Node(value);
return true;
}
//Starting from root
Node currentNode = root;
//Traversing the tree untill valid position to insert the value
while (currentNode != null) {
Node leftChild = currentNode.getLeftChild();
Node rightChild = currentNode.getRightChild();
//If the value to insert is less than root value then move to left subtree
//else move to right subtree of root
//and before moving check if the subtree is null, if it's then insert the value.
if (currentNode.getData() > value) {
if (leftChild == null) {
leftChild = new Node(value);
currentNode.setLeftChild(leftChild);
return true;
}
currentNode = leftChild;
} else {
if (rightChild == null) {
rightChild = new Node(value);
currentNode.setRightChild(rightChild);
return true;
}
currentNode = rightChild;
} //end of else
} //end of while
return false;
}
//Function to check if Tree is empty or not
public boolean isEmpty()
{
return root == null; //if root is null then it means Tree is empty
}
//Just for Testing purpose
public void printTree(Node current)
{
if (current == null) return;
System.out.print(current.getData() + ",");
printTree(current.getLeftChild());
printTree(current.getRightChild());
}
}

Explanation

Add function takes an integer value and then traverses the BST tree for a valid position to insert a value. It starts from the root of the tree and traverses the leaf node. Traversing is based on the BST formula, i.e. if the current node’s value is less than key-value, then we will have to find an appropriate position in the right subtree of the current node before we try to find a position in the left subtree.

When we reach the leaf node, ...