...

/

Insertion in BST (Complete Implementation)

Insertion in BST (Complete Implementation)

This chapter will cover the implementation of Binary Search Tree insertion in Java by using the iterative and recursive 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)

Press + to interact
main.java
binarySearchTree.java
Node.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, ...