PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q6(a)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

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 :

  1. Locate and its parent .
  2. Let child = (X->left != NULL) ? X->left : X->right.
  3. If is the root (P == NULL), update root = child.
  4. Otherwise, if is P->left, set P->left = child; else set P->right = child.
  5. 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
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.

All past exam questions for Data Structure and Algorithms