In a binary search tree the following must hold:

  1. Greater keys are in the right-subtree
  2. Smaller or EQUAL keys belong to the left-subtree

All the algorithms I found to delete a node start by finding the smallest node in the right subtree of the node we want to delete, the successor (or the greatest node in the left subtree, the predecessor), and replace the deleted node for the successor.

But what happens when BST nodes with the same key exist and we use the successor method?

If we use the predecessor, we don't run into this problem.

   /   \
  2     5 <-- Delete 5
 / \   / \
1  3  5   7
         / \
       [7]  9 <-- 7 will take 5's place

Now we end up with:

   /   \
  2     7 
 / \   / \
1  3  5  [7]  <-- This 7 should be in the left subtree

The BST will still work (or not?), but the definition of BST won't fit this resultant tree anymore.

Is there another algorithm that takes this into account or is this result expected and generally accepted?

  • $\begingroup$ (Is there any problem replacing the node to delete by its predecessor?) $\endgroup$
    – greybeard
    Jan 25, 2020 at 22:58
  • $\begingroup$ @greybeard No, it works, but they say we can do it with both predecessor and successor (most often with the successor). I'll update the question to say predecessor works with no issues. $\endgroup$
    – jpenna
    Jan 25, 2020 at 23:22
  • $\begingroup$ BST will still work [when replacing a node to delete with its successor] (or not?) You can take advantage of a search tree when a single key comparison lets you ignore part of the tree. Here, that would no longer be possible for equal keys. $\endgroup$
    – greybeard
    Jan 26, 2020 at 0:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.