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.