Past exam question: 2076 Baisakh (Back), Q8(a)
Open in the Padhaiko appExplain deletion of node with two children in BST with suitable example.
Solution
Rule for Deleting a BST Node with Two Children: When node has both a non-empty left subtree and a non-empty right subtree, removing directly would disconnect two branches. To preserve the BST ordering invariant (), replace 's key with either:
- Its in-order successor (the minimum key in 's right subtree — leftmost node of
X->right), or - Its in-order predecessor (the maximum key in 's left subtree — rightmost node of
X->left).
Because the in-order successor has no left child (at most one child: right child), deleting that successor node reduces cleanly to the leaf or single-child BST deletion case.
Example: Delete 50 from BST:
50 60
/ \ inorder / \
30 70 succ = 60 30 70
/ \ ========> \
60 80 80
- Find in-order successor of
50: leftmost node in right subtree7060. - Copy
60into node50. - Delete leaf
60from70's left child.
In-order traversal remains sorted: 30, 60, 70, 80.
To delete a BST node with two children, copy its in-order successor (smallest key in X->right) or in-order predecessor (largest key in X->left) into , then recursively delete that successor/predecessor node (which has at most one child).