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:

Case1: Deleting a leaf node

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:

**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

TRENDING TOPICS