How would you perform deletion in a Binary Search Tree?

Unlike insertion, deletion is a wee bit complex when it comes to Binary Search Trees. That's because while insertion you don't need to worry about rearranging the BST, you just find its correct location and done. The node will always be added as a leaf node. On the other hand in deletion you may have the need to delete any non leaf node as well and that's where it becomes tricky. You need to maintain the sorted order of the BST while deleting this one. The various possible delete options and the approaches to handle them are liste below

1. Deleting a node with no children: simply remove the node from the tree.
2. Deleting a node with one child: remove the node and replace it with its child.
3. Deleting a node with two children: This one is tricky. You need to search for the node and replace its value with the minimum value on the right sub tree of that node. Don't delete the node as yet. Traverse to the right sub tree and delete the minimum value node whose value you copied to the node to be deleted. This minimum value node will be either of the first 2 cases and can be deleted easily.

Example of all 3 cases below using the following BST.

We are using the same TreeNode class as in previous examples. Check the other examples out here.

public static boolean remove(TreeNode node, int val, TreeNode parent){
if (val<node.value){
	if (node.left!=null){
		return remove(node.left,val,node);
	}
	else return false;
}else if (val>node.value){
	if (node.right!=null){
		return remove(node.right,val,node);
	}
	else return false;
}else{
	if (node.left!=null && node.right!=null){ //Case 3
		node.value=getMinimum(node.right).value;
		remove(node.right, node.value, node);
	}else if (parent!=null && parent.left==node){ //Case 1&2
		parent.left=(node.left != null) ? node.left : node.right;
	}else if (parent!=null && parent.right == node) { //Case 1&2
        parent.right = (node.left != null) ? node.left : node.right;
  }
	return true;
}
}

Test code below. It deletes node with value 3 since its the case 3. You can try out with other nodes

public class BSTUtil {
public static void main(String[] args) {
TreeNode root=new TreeNode(8);
TreeNode.insert(root, new TreeNode(3));
TreeNode.insert(root, new TreeNode(10));
TreeNode.insert(root, new TreeNode(6));
TreeNode.insert(root, new TreeNode(1));
TreeNode.insert(root, new TreeNode(14));
TreeNode.insert(root, new TreeNode(4));
TreeNode.insert(root, new TreeNode(7));
TreeNode.insert(root, new TreeNode(13));

StringBuffer preorderbuf=new StringBuffer();
TreeNode.getPreOrder(root, preorderbuf);
System.out.println("Pre order tree before deletion"+preorderbuf);
TreeNode.remove(root, 3, null);
preorderbuf=new StringBuffer();
TreeNode.getPreOrder(root, preorderbuf);
System.out.println("Pre order tree after deletion "+preorderbuf);
}
}

Output for above test code is as follows

Pre order tree before deletion 8 3 1 6 4 7 10 14 13
Pre order tree after deletion  8 4 1 6 7 10 14 13

 

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself