Consider BST deletion of a node z

Consider BST deletion of a node \(z\). Case 0: \(z\) has no children. Case 1: \(z\) has exactly one child. Case 2: \(z\) has two children. Write complete pseudocode \(\mathrm{TREE}\text{-}\mathrm{DELETE}(T, z)\) that handles all three cases, using parent pointers, and that in Case 2 replaces \(z\)'s key by its successor \(y\) and then splices \(y\) out of the tree (\(y\) has no left child). Prove that after \(\mathrm{TREE}\text{-}\mathrm{DELETE}\), the BST property holds on the remaining keys. Your proof must treat Case 2 separately and must argue that moving \(y\)'s key into \(z\)'s node cannot violate the BST property at \(z\) or at any ancestor of \(z\).

Zero- and one-child deletions are splices: the parent of \(z\) is rewired to \(z\)’s unique child (or to \(\mathrm{NIL}\)). Two-child deletion cannot splice \(z\) without losing a subtree.