Skip to main content

Data Structures · Search trees and balanced trees

Consider BST deletion of a node z

Problem

Data Structures practice problem

Consider BST deletion of a node zz.
Case 0: zz has no children. Case 1: zz has exactly one child. Case 2: zz has two children.
Write complete pseudocode TREE-DELETE(T,z)\mathrm{TREE}\text{-}\mathrm{DELETE}(T, z) that handles all three cases, using parent pointers, and that in Case 2 replaces zz's key by its successor yy and then splices yy out of the tree (yy has no left child). Prove that after TREE-DELETE\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 yy's key into zz's node cannot violate the BST property at zz or at any ancestor of zz.

Hint

Hint

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

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.

More Data Structures practice problems

Back to Data Structures

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.