Deletion in binary search tree (BST) in Java

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.

Delete a node in a binary search tree

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:

Case1: Deleting a leaf node
1 of 3

Code example

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);
}
}

Explanation

Let’s understand the above code implementation:

  • Lines 1–9: We define the Node class, which stands for a binary tree node.
    • Line 2: We define an integer data to store the value of the node.
    • Line 3: We declare two references of type Node with the names left and right, which stand in for the current node’s left and right child nodes, respectively.
    • Line 5: We define the Node class constructor. It initializes the node with the value supplied as an integer parameter named value.
    • Line 7: We set the left and right child references to null.
  • Lines 11–80: We define a class named BST.
    • Line 12: We declare a Node variable named root.
    • Lines 14–16: We define the BinarySearchTree class constructor. We set the root variable in this constructor to null to represent an empty tree.
    • Line 22–35: We insert the new node into the BST.
    • Line 37–39: We delete a 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.
    • Line 42–44: If the root is null, indicating an empty tree or the value is not found, it returns the root.
    • Line 46–47: If the value is less than the root value, recursively call the deleteNode() method on the left subtree.
    • Line 48–49: If the value is greater than the root value, recursively call the deleteNode() on the right subtree.
    • Line 50–58: If the value is equal to the 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).
    • Line 61: We return the updated root.
    • Line 64–71: We set the 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.
  • Line 84: We create an instance named tree of the BST class.
  • Lines 85–91: We insert several values into the tree using the insertValue() method.
  • Lines 93–94: We call the printTree() method on the tree object, passing the root of the tree to print its elements in the in-order traversal.
  • Line 96: We call the deleteValue() method to remove 20 from the tree.
  • Lines 97–98: We call the printTree() method on the tree object, passing the root of the tree to print its elements after the deletion.
Copyright ©2024 Educative, Inc. All rights reserved