Deleting

We want to delete a node i.

• If i has zero kids, delete it.
• If i has one kid, delete i and move i's kid into i's place.
• If i has two kids, let j be the successor of i. Delete j in place (it only has one kid, so that's easy). Now, move j into i's place.

Why is this well defined? In particular, how do we know that j only has one child?