Deletion in BST in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Deletion Cases in BST

Which of the following correctly describes the case when deleting a node with two children in a Binary Search Tree (BST)?

A Delete the node and then reinsert all nodes from its right subtree.

B Simply remove the node and connect its left child directly to its parent.

C Replace the node with its left child only, ignoring the right subtree.

D Replace the node with its in-order predecessor or successor, then delete that predecessor or successor node.

💡 Hint

Think about how to maintain BST properties after deletion.

When deleting a node with two children, we replace it with its in-order predecessor (maximum node in left subtree) or in-order successor (minimum node in right subtree) to maintain BST order. Then we delete that predecessor or successor node, which will have at most one child.

📋 Factual

intermediate

Number of Children in BST Deletion

How many children can a node have in a BST when it is deleted using the simplest case?

A Zero or one child

B Exactly two children

C At least one child

D Any number of children

💡 Hint

Consider the easiest deletion cases first.

The simplest deletion cases in BST are when the node has zero or one child. These cases are straightforward because the node can be removed or replaced by its single child without violating BST properties.

🔍 Analysis

advanced

Result of Deleting Root Node with Two Children

Given a BST where the root node has two children, what will be the root node's value after deleting the root?

Data Structures Theory

Initial BST root value: 15
Root has left child 10 and right child 20.
After deleting root, which value replaces it?

A 10

B The minimum value in the right subtree

C 20

D The maximum value in the left subtree

💡 Hint

Recall the in-order successor concept.

When deleting a node with two children, the node is replaced by its in-order successor, which is the minimum value in its right subtree. This maintains BST order.

❓ Comparison

advanced

Comparing In-Order Predecessor and Successor in Deletion

Which statement correctly compares using the in-order predecessor versus the in-order successor when deleting a node with two children in a BST?

A Both maintain BST properties, but predecessor is maximum in left subtree, successor is minimum in right subtree.

B Predecessor is always smaller than the node, successor is always larger, so only successor can be used.

C Predecessor and successor are the same node, so either can be used interchangeably without difference.

D Using predecessor breaks BST properties, only successor maintains correct order.

💡 Hint

Think about where predecessor and successor come from in the BST.

The in-order predecessor is the maximum node in the left subtree, and the in-order successor is the minimum node in the right subtree. Both can replace the deleted node to maintain BST properties.

❓ Reasoning

expert

Effect of Deleting a Leaf Node on BST Height

What is the effect on the height of a BST after deleting a leaf node?

A The height increases because the tree becomes unbalanced.

B The height remains the same because leaf nodes do not affect height.

C The height decreases by one only if the leaf was on the longest path.

D The height always decreases by one regardless of the leaf's position.

💡 Hint

Consider how height is defined in a tree.

The height of a BST is the length of the longest path from root to a leaf. Deleting a leaf node only decreases height if that leaf was on the longest path. Otherwise, height remains unchanged.