AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumbstdeletion

~75s

Deleting the root of a BST

A BST has 50 at the root, 30 and 70 as its children, 20 and 40 below 30, and 60 and 80 below 70. The root is deleted and replaced by its inorder successor. Which key becomes the new root?

Show the answer and the worked solution

Correct answer: D.

60

Worked solution

  1. The inorder successor of a node with two children is the smallest key in its right subtree.
  2. The right subtree of 50 is rooted at 70, with 60 on its left and 80 on its right.
  3. The leftmost key there is 60, so 60 moves up to the root and its old slot is freed.

Answer: 60.

The idea

Replacing a deleted node with its inorder successor (or predecessor) is the only substitution that preserves the BST ordering, because it is the key immediately adjacent in sorted order.

Shortcut. The inorder successor is the next larger key: in 20, 30, 40, 50, 60, 70, 80 the key after 50 is 60.

Common trap. 40 is the inorder predecessor, the largest key in the left subtree; it is a valid replacement in general, but not the successor asked for.

Data Structures & Algorithms

17 of 40

Level

Medium

Target time

~75s

PreviousNext
AI InterviewGet started

Deleting the root of a BST — Aptitude Question

Deleting the root of a BST: A BST has 50 at the root, 30 and 70 as its children, 20 and 40 below 30, and 60 and 80… Answer and worked solution on CodeKairo.

Question

A BST has 50 at the root, 30 and 70 as its children, 20 and 40 below 30, and 60 and 80 below 70. The root is deleted and replaced by its inorder successor. Which key becomes the new root?

Options

  1. 20
  2. 30
  3. 40
  4. 60
Show the answer and the worked solution

Correct answer: D. 60

Worked solution

  1. The inorder successor of a node with two children is the smallest key in its right subtree.
  2. The right subtree of 50 is rooted at 70, with 60 on its left and 80 on its right.
  3. The leftmost key there is 60, so 60 moves up to the root and its old slot is freed.

Answer: 60.

The idea

Replacing a deleted node with its inorder successor (or predecessor) is the only substitution that preserves the BST ordering, because it is the key immediately adjacent in sorted order.

Shortcut. The inorder successor is the next larger key: in 20, 30, 40, 50, 60, 70, 80 the key after 50 is 60.

Common trap. 40 is the inorder predecessor, the largest key in the left subtree; it is a valid replacement in general, but not the successor asked for.

All Data Structures & Algorithms questions · placement mock tests