We must always follow the below 2 points when deleting a node from Binary Search Tree:
- Delete the node.
- Retain the Binary Search Tree property.
Consider the following scenarios that we encounter when deleting a node from a BST:
Scenario 1: Deleting a leaf node or a childless node.
This is certainly the easiest case you can encounter. Since the node to be deleted has no children, we just delete the node and the BST property remains unaltered.
Scenario 2: Deleting a node with one child.
Delete the node, and make the node’s parent, the parent of its only child.
Scenario 3: Deleting a node with 2 children.
Before going to the deletion, lets understand how do we know if a binary tree is Binary Search Tree – The Inorder traversal of a Binary Search Tree is always sorted. Now lets understand what the below 2 terms mean in this case:
- Predecessor: A predecessor of a node is the element which appears before that node in an Inorder traversal of a BST.
– In a BST, its the rightmost node of the left subtree. - Successor: A successor of a node is the element which appears after that node in an Inorder traversal of a BST.
– In a BST, its the leftmost node of the right subtree.Consider the following BST:
Deletion: Now that you understand the terms predecessor and successor. When you want to delete a node with 2 children, follow the below steps:
- Replace the node to be deleted with either its predecessor or successor.
- Delete the respective predecessor or the successor from the tree.
In the tree below, I am replacing the node to be deleted(17) with its successor(19), and then deleting the successor(19) from the tree.
Note that Inorder traversal after the deletion is still sorted retaining the property of a BST as shown below: