ITPEC FE Subject B October 2025 Question 13

BST node removal with in-order successor

When deleting a node with two children, the standard approach is to replace it with its in-order successor (smallest node in the right subtree).

Algorithm for the `else` branch (both children exist):
1. node2 ← node.right — start at the right child
2. while (node2.left is not undefined) — walk left to find the minimum
3. node2 ← node2.left
4. node.key ← node2.key — copy successor's key into the current node
5. node.right ← remove(node.right, node2.key) — delete the successor from the right subtree

Why `node.right` (not `node.left`) for blank A:
- The in-order successor lives in the right subtree by definition

Why `node2.left is not undefined` (not `node2.key < key`) for blank B:
- The goal is to reach the leftmost node — a structural traversal, not a key comparison

Why `node2.key` (not `key`) for blank C:
- After copying the successor's key, we must remove the successor node itself, identified by node2.key

Key rule: In BST deletion with two children, always find the in-order successor (min of right subtree) or in-order predecessor (max of left subtree), copy its value, then recursively delete that successor/predecessor node.

AI-generated — may contain errors