A Java data structure called a binary search tree (BST) enables quick searching, insertion, and removal of components. Each node in this binary tree has a value, and for any given node, all values in its left subtree are less than its value and all values in its right subtree are greater than its value.
BSTs have a diverse range of applications. From spell checkers to address lookup and packet forwarding in routers, and from game development to data compression, there are many applications that use BSTs for fast lookups and retrievals.
There are three cases that can occur while deleting a node from a BST. Let’s see these cases one by one.
Case 1: Delete a leaf node
In BST, deleting a leaf node is easy. Since there is no node smaller than it in the tree, just delete it.
Case 2: Delete a node with only one child
In BST, removing just one child node is likewise straightforward. The node is deleted when the child is copied to it.
Case 3: Delete a node with both children
It is more difficult to delete a node that has both children. In this case, we must remove the node in such a way that the new tree has the features of a BST.
The difficulty is to locate the node’s in-order successor. Copy the contents of the in-order successor to the node, then remove it.
Let’s see the deletion visually:
Let’s now see how deletion works in the BST in Java.
class Node {int data;Node left, right;public Node(int data) {this.data = data;left = right = null;}}class BST {Node root;public BST() {root = null;}public void insertValue(int data) {root = insertNode(root, data);}private Node insertNode(Node root, int data) {if (root == null) {root = new Node(data);return root;}if (data < root.data) {root.left = insertNode(root.left, data);} else if (data > root.data) {root.right = insertNode(root.right, data);}return root;}public void deleteValue(int data) {root = deleteNode(root, data);}private Node deleteNode(Node root, int data) {if (root == null) {return root;}if (data < root.data) {root.left = deleteNode(root.left, data);} else if (data > root.data) {root.right = deleteNode(root.right, data);} else {if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;}root.data = minValue(root.right);root.right = deleteNode(root.right, root.data);}return root;}private int minValue(Node root) {int minValue = root.data;while (root.left != null) {minValue = root.left.data;root = root.left;}return minValue;}public void printTree(Node node) {if (node != null) {printTree(node.left);System.out.print(node.data + " ");printTree(node.right);}}}public class Main {public static void main(String[] args) {BST tree = new BST();tree.insertValue(50);tree.insertValue(30);tree.insertValue(20);tree.insertValue(40);tree.insertValue(70);tree.insertValue(60);tree.insertValue(80);System.out.println("BST values:");tree.printTree(tree.root);tree.deleteValue(20);System.out.println("\nAfter removing 20 from the BST:");tree.printTree(tree.root);}}
Let’s understand the above code implementation:
Node
class, which stands for a binary tree node.
Node
with the names left
and right
, which stand in for the current node’s left
and right
child nodes, respectively.Node
class constructor. It initializes the node with the value supplied as an integer parameter named value
.left
and right
child references to null
.BST
.
Node
variable named root
.BinarySearchTree
class constructor. We set the root
variable in this constructor to null
to represent an empty tree.node
with the given value from the binary search tree by calling the deleteNode()
method and updating the root node with the modified tree structure.null
, indicating an empty tree or the value is not found, it returns the root
.root
value, recursively call the deleteNode()
method on the left subtree.root
value, recursively call the deleteNode()
on the right subtree.root
value, handle three cases: no left child (return the right child), no right child (return the left child), and both left and right children (find the minimum value in the right subtree, replace the root value with it, and recursively delete the minimum value from the right subtree).root
.minValue
to the value of the root
node as its initial value. Until we reach the leftmost leaf node, we loop over the left
subtree of the root
node, updating minValue
with the value of the current node each time. We, then, return the minValue
, which contains the lowest value discovered in the binary search tree.tree
of the BST
class.insertValue()
method.printTree()
method on the tree object, passing the root of the tree to print its elements in the in-order traversal.deleteValue()
method to remove 20 from the tree
.printTree()
method on the tree object, passing the root of the tree to print its elements after the deletion.