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.
Insertion Implementation (Iterative)
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 BSTpublic boolean add(int value) {//If Tree is empty then insert Root with the given value inside Treeif (isEmpty()) {root = new Node(value);return true;}//Starting from rootNode currentNode = root;//Traversing the tree untill valid position to insert the valuewhile (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 whilereturn false;}//Function to check if Tree is empty or notpublic boolean isEmpty(){return root == null; //if root is null then it means Tree is empty}//Just for Testing purposepublic 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, ...