Binary Search Tree - node deletion

Question

I am trying to understand why when deleting a node in a BST tree and having to keep the children and adhering to the BST structure, you have to either take the node's right child (higher value, then node being deleted) and if that right child has a left child take that child. Else just the the node being deleted right child.

Why don't you just take the node being deleted left child, if there's one. It still works out correctly?

Or have I missed something.

I'm reading this article.

Answer 1

You're oversimplifying.

The node selected to replace the one that was deleted must be larger than all the nodes to the left of the deleted one, and smaller than all the nodes to the right. So it must be either the left subtree's rightmost descendant or the right subtree's leftmost descendant; except if one or the other subtree is entirely absent, we can remove a level of tree entirely simply by replacing the deleted node with the child that was present.

The rules listed in the article will always give you the right subtree's leftmost descendant when both trees are present. If you wished, you could indeed derive an alternative ruleset that used the leftmost subtree's rightmost descendant instead.

It does not "work out correctly" to just always use the left child. Indeed, if there is a child on the right and the left child itself has two children, it cannot even be done without essentially rebuilding the tree.

Answer 2

You would be correct for the special case that you described. But for something more general where you can have many more levels deeper than the node being deleted you need to replace that node with a node that will be less than everything to the right, and greater than everything to the left. So as an example:

   2
 /  \
1    6
    / \
   4   7
    \
     5  

Let's say you wanted to move the node 6, now following your instructions we will replace it with the left child, node 4. Now what do we do with node 5? We could make it the left child of node 7 (or the left most descendant of node 7 if it existed), but why would you do all this reshuffling when you know that removing a leaf is trivial and you just want to replace the node with another node that would keep every node on the left less and every node on the right greater.