Algorithm to delete a node from a binary search tree
Step 1: IF TREE = NULL
Write "VAL not found in the tree"
ELSE IF VAL < TREE DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE -> DATA
Delete(TREE -> RIGHT, VAL)
ELSE IF TREE -> LEFT AND TREE -> RIGHT
SET TEMP = findLargestNode(TREE -> LEFT)
SET TREE -> DATA = TEMP -> DATA
Delete(TREE -> LEFT, TEMP -> DATA)
ELSE SET TEMP = TREE
IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL
SET TREE = NULL
ELSE IF TREE -> LEFT != NULL
SET TREE = TREE -> LEFT
ELSE
SET TREE = TREE -> RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
Step 2: END
Explanation
- In Step 1 of the algorithm, we first check if TREE=NULL, because if it is true, then the node to be deleted is not present in the tree.
- However, if that is not the case, then we check if the value to be deleted is less than the current node’s data.
- In case the value is less, we call the algorithm recursively on the node’s left sub-tree, otherwise the algorithm is called recursively on the node’s right sub-tree.
- Note that if we have found the node whose value is equal to VAL, then we check which case of deletion it is.
- If the node to be deleted has both left and right children, then we find the in-order predecessor of the node by calling findLargestNode(TREE -> LEFT) and replace the current node’s value with that of its in-order predecessor.
- Then, we call Delete(TREE -> LEFT, TEMP -> DATA) to delete the initial node of the in-order predecessor. Thus, we reduce the case 3 of deletion into either case 1 or case 2 of deletion.