Why is this line necessary in this code to delete from a BST?

Question

I'm trying to learn more about binary trees and I came across a method on how to find a successor node (when trying to delete a node), I'm having a hard time understanding part of it. Here's the code.

    private Node getSuccessor(Node delNode){
    Node successorParent = delNode;
    Node successor = delNode;
    Node current = delNode.rightChild;

    while(current != null){
        successorParent = successor;
        successor = current;
        current = current.leftChild;
    } // end of if

    if(successor != delNode.rightChild){
        successorParent.leftChild = successor.rightChild;
        successor.rightChild = delNode.rightChild;
    }
    return successor;


}

I completely understand the while loop and what's happing in there. What I don't understand is the if statement and specifically...

successor.rightChild = delNode.rightChild;

why would I want to assign the right child of delNode to the right child of successor node? Why is the if statement necessary?

Answer 1

What getSuccessor() does, is find the successor of delNode, which is the node with the smallest value greater than delNode, i.e. the leftmost node in the right subtree under delNode. It then removes it from the right subtree, and attaches the right subtree to the right under the successor.

The reason for the conditional is that if the successor is the right child of delNode, it is already at the top of the right subtree, and it doesn't need to be taken out of the subtree and moved to the top of it.

In a next step, delNode will be deleted, successor will be attached to delNode's parent, and the left subtree under delNode will be attached to the left under the successor. The effect of all this is to replace delNote with its successor.

(This method is not the most straightforward way to remove a node from a binary tree. You could simply attach the right subtree to delNode's parent, and the left subtree to the left under successor. But this more complicated method has the advantage of not increasing the height of the tree, because every node stays at the same depth, or is moved closer to the root.)

Here's an example where we're going to delete node 3: we find that its successor is 4, we remove 4 from the right subtree and place it at the top of the subtree, then we replace node 3 by the successor 4 and attach the left subtree to it:

      9                                                9
     / \                                              / \
    3  ...                        4                  4  ...
   / \                             \                / \
  2   6              6              6              2   6
 /   / \            / \            / \            /   / \
1   4   7          4   7          5   7          1   5   7
     \   \          \   \              \                  \
      5   8          5   8              8                  8

(You'll notice that after removing the node, every node is either at the same depth it was before, or has moved closer to the root, so the tree's height hasn't increased.)

Now consider an example where again we're going to delete node 3, but we find that its successor, node 4, is already at the top of the right subtree; that means we can immediately replace node 3 by the successor 4 and attach the left subtree to it, without first having to move node 4 to the top of the right subtree:

      8                                 8
     / \                               / \
    3  ...                            4  ...
   / \                               / \
  2   4              4              2   6
 /     \              \            /   / \
1       6              6          1   5   7
       / \            / \         
      5   7          5   7        

Answer 2

There are two cases that this code is trying to account for. The first is where you're deleting a node X whose successor Y is its immediate right child:

X
 \
  Y
   \
    Z

In this case, we're ultimately going to replace X with Y, so the method can just return Y and say "here's the node that now replaces X."

On the other hand, suppose that X's successor Y is in a subtree of its right child tree:

X
 \
  A
 / \
Y   C
 \
  B

In this case, we can't blindly replace X with Y, because doing so will lose the node A and everything in subtree C. So before we say "hey tree - go replace node X with node Y," we rearrange the nodes in the tree so that they look like this:

X
 \
  Y
   \
    A
   / \
  B   C

Now, when we replace X with Y, we haven't lost any of the other nodes in the tree.

The shape here, by the way, is formed by swapping X and Y, then deleting X (which is in the spot Y used to be in) by making Y's former parent have Y's former right subtree as its left child. Trace through those lines and see if you can see how this works.