Deletion in Binary Search Trees (Implementation)
We will cover the implementation of deletion, including all the cases that we discussed previously: Node as a Leaf, Parent Node with one child, and Parent Node with two children.
Deletion Cases
Following are the three cases of deletion in a Binary Search Tree:
- Node is a leaf node
- Node has a one child
- Node has two children
Implementation in Java
Look at the code snippet below and try to understand the code. If you don’t understand at any point, you can just read the explanation below.
class binarySearchTree {private Node root;public Node getRoot() {return root;}public void setRoot(Node root) {this.root = root;}//3 conditions for delete//1.node is leaf node.//2.node has 1 child.//3.node has 2 children.boolean delete(int value, Node currentNode) {if (root == null) {return false;}Node parent = null; //To Store parent of currentNodewhile(currentNode != null && (currentNode.getData() != value)) {parent = currentNode;if (currentNode.getData() > value)currentNode = currentNode.getLeftChild();elsecurrentNode = currentNode.getRightChild();}if(currentNode == null) {return false;}else if(currentNode.getLeftChild() == null && currentNode.getRightChild() == null) {//1. Node is Leaf Node//if that leaf node is the root (a tree with just root)if(root.getData() == currentNode.getData()){setRoot(null);return true;}else if(currentNode.getData() < parent.getData()){parent.setLeftChild(null);return true;}else{parent.setRightChild(null);return true;}} else if(currentNode.getRightChild() == null) {if(root.getData() == currentNode.getData()){setRoot(currentNode.getLeftChild());return true;}else if(currentNode.getData() < parent.getData()){parent.setLeftChild(currentNode.getLeftChild());return true;}else{parent.setRightChild(currentNode.getLeftChild());return true;}}else if(currentNode.getLeftChild() == null) {if(root.getData() == currentNode.getData()){setRoot(currentNode.getRightChild());return true;}else if(currentNode.getData() < parent.getData()){parent.setLeftChild(currentNode.getRightChild());return true;}else{parent.setRightChild(currentNode.getRightChild());return true;}}else {//Find Least Value Node in right-subtree of current NodeNode leastNode = findLeastNode(currentNode.getRightChild());//Set CurrentNode's Data to the least value in its right-subtreeint temp = leastNode.getData();delete(temp, root);currentNode.setData(temp);//Delete the leafNode which had the least valuereturn true;}}//Helper function to find least value node in right-subtree of currentNodeprivate Node findLeastNode(Node currentNode) {Node temp = currentNode;while (temp.getLeftChild() != null) {temp = temp.getLeftChild();}return temp;}//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
Let’s break the above code down into different sections:
-
Main function
– Creates BST and calls the delete function. -
Delete function
– Takes the node value to be deleted and the root node. It returns a boolean for successful/unsuccessful deletion. -
findLeastNode
– Takes in the root node of the right sub-tree on the node to be deleted, and returns the least value node in ...