Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Node Representation for Deletion
For deletion each node also stores a parent pointer, so a node ref has ref.left, ref.right, ref.data and ref.parent. Deletion must keep the BST property that insertion also keeps.
BSTreplace: One or No Child
BSTreplace(root, ref) removes a node ref that has at most one child:
- if
refis the root, its child becomes the new root, stop - if
refis neither root nor leaf, its only child takes its place as the child ofref.parent, stop - if
refis a leaf, set the matching child pointer ofref.parenttoNone, stop

def BSTreplace(root, ref): # ref has one or no child
if ref.left is None:
child = ref.right
else:
child = ref.left
if ref == root: # deleting the root
if child is not None:
child.parent = None
return child # child is the new root
if ref.parent.left == ref: # is ref a left child?
ref.parent.left = child
else:
ref.parent.right = child
if child is not None:
child.parent = ref.parent # keep the parent pointer right
return rootSince child is None for a leaf, the same code covers the leaf case: the parent simply gets a None child.
Example: One Child, Not Root
Deleting , whose only child is : becomes the right child of and its parent pointer is updated to . In short, a node with one child is replaced by that child.

Two Children
A node with two children cannot simply be cut out. Instead:
- step 1: find the successor
succ, the minimum value in the right subtree, by going right once and then left until there is no left child - step 2: copy its value into the node to delete,
ref.data = succ.data - step 3: delete
succwithBSTreplace, which works becausesucchas no left child
def BSTdelete_two_children(root, ref):
succ = ref.right
while succ.left is not None: # step 1
succ = succ.left
ref.data = succ.data # step 2
return BSTreplace(root, succ) # step 3Example: Delete 5
The right subtree of is rooted at . Going left from reaches and then , which has no left child, so succ is .

The value is replaced by , and the old node is removed with BSTreplace, so its child moves up.

Choosing the minimum of the right subtree is a convention. The maximum of the left subtree would work equally well, which is why the definitions sheet says these implementation choices are not part of the BST definition.