Past exam question: 2075 Baisakh (Back), Q6(a)
Open in the Padhaiko appQuestion
Explain deletion of node with one child in BST with suitable example.
Solution
Rule for Deleting a BST Node with One Child: When a target node has exactly one child (either only X->left or only X->right), deleting simply bypasses :
- Locate and its parent .
- Let
child = (X->left != NULL) ? X->left : X->right. - If is the root (
P == NULL), updateroot = child. - Otherwise, if is
P->left, setP->left = child; else setP->right = child. - Free . Because all keys in
child's subtree already sit on the correct side of , the BST property holds automatically.
Example: Delete 30 from BST:
50 50
/ \ bypass 30 / \
30 70 ========> 20 70
/
20
30is50->leftand has one child (20on its left).- Link
50->left = 20and free30. In-order traversal20, 50, 70remains valid.
Answer:
To delete a BST node with one child, bypass it by linking its parent directly to its single non-null child (updating root if the deleted node was the root) and freeing the node.