PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q8(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 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:

  1. Its in-order successor (the minimum key in 's right subtree — leftmost node of X->right), or
  2. 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
  1. Find in-order successor of 50: leftmost node in right subtree 70 60.
  2. Copy 60 into node 50.
  3. Delete leaf 60 from 70's left child.

In-order traversal remains sorted: 30, 60, 70, 80.

Answer:

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).

All past exam questions for Data Structure and Algorithms