Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

Saying a node has two children is equivalent to saying a node has both a left subtree and a right subtree. We know that the predecessor is the minimum value of the left subtree and the predecessor is the maximum value of the right subtree.

Suppose that our node with 2 children \(x\)’s predecessor \(p\) had a right child. By the binary-search-tree property, this child must be both greater than \(p\) and less than \(x\). But this cannot be the case, otherwise \(p\)’s right child would be \(x\)’s predecessor, not \(p\).

An equivalent proof by contradiction ensures that \(x\)’s successor has no left child.