BST Delete Operation in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a leaf node in BST

What is the output of the BST inorder traversal after deleting the leaf node 20?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left) current = current->left;
    return current;
}

Node* deleteNode(Node* root, int key) {
    if (!root) return root;
    if (key < root->val) root->left = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        Node* temp = minValueNode(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

void inorder(Node* root, std::vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

int main() {
    Node* root = nullptr;
    int vals[] = {50, 30, 20, 40, 70, 60, 80};
    for (int v : vals) root = insert(root, v);
    root = deleteNode(root, 20);
    std::vector<int> result;
    inorder(root, result);
    for (int v : result) std::cout << v << " ";
    return 0;
}

A [30, 40, 50, 60, 70]

B [20, 30, 40, 50, 60, 70, 80]

C [30, 40, 50, 60, 70, 80]

D [20, 30, 40, 50, 60, 70]

💡 Hint

Deleting a leaf node removes it without affecting other nodes.

Deleting 20, which is a leaf, removes it from the tree. The inorder traversal then lists all remaining nodes in sorted order without 20.

❓ Predict Output

intermediate

Output after deleting a node with one child in BST

What is the inorder traversal output after deleting node 30 which has one child?

DSA C++

/* Same code as previous challenge with deletion of 30 instead of 20 */
int main() {
    Node* root = nullptr;
    int vals[] = {50, 30, 40, 70, 60, 80};
    for (int v : vals) root = insert(root, v);
    root = deleteNode(root, 30);
    std::vector<int> result;
    inorder(root, result);
    for (int v : result) std::cout << v << " ";
    return 0;
}

A [20, 30, 40, 50, 60, 70, 80]

B [40, 50, 60, 70, 80]

C [20, 50, 60, 70, 80]

D [20, 40, 50, 60, 70, 80]

💡 Hint

When deleting a node with one child, the child replaces the node.

Node 30 has one child (40). After deletion, 40 replaces 30. The inorder traversal reflects this change.

❓ Predict Output

advanced

Output after deleting a node with two children in BST

What is the inorder traversal output after deleting node 50 which has two children?

DSA C++

/* Same code as previous challenges with deletion of 50 */
int main() {
    Node* root = nullptr;
    int vals[] = {50, 30, 20, 40, 70, 60, 80};
    for (int v : vals) root = insert(root, v);
    root = deleteNode(root, 50);
    std::vector<int> result;
    inorder(root, result);
    for (int v : result) std::cout << v << " ";
    return 0;
}

A [20, 30, 40, 50, 60, 70, 80]

B [30, 40, 60, 70, 80]

C [20, 30, 40, 70, 60, 80]

D [20, 30, 40, 60, 70, 80]

💡 Hint

When deleting a node with two children, replace it with its inorder successor.

Node 50 is replaced by its inorder successor 60. Then 60 is deleted from its original position. The inorder traversal reflects the updated tree.

🔧 Debug

advanced

Identify the error in BST delete function

What error will occur when running this deleteNode function if the node to delete has two children?

DSA C++

Node* deleteNode(Node* root, int key) {
    if (!root) return root;
    if (key < root->val) root->left = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        Node* temp = root->right; // Error here: should find minValueNode
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

A The code will produce incorrect BST structure because it uses root->right instead of minValueNode.

B The code will cause a runtime error due to deleting wrong node.

C The code will cause a memory leak because nodes are not deleted.

D The code will compile but cause a segmentation fault due to null pointer dereference.

💡 Hint

Check how the inorder successor is found in the delete function.

The code uses root->right directly instead of finding the minimum node in the right subtree. This breaks BST property after deletion.

🧠 Conceptual

expert

Number of nodes after multiple deletions in BST

Given a BST with nodes inserted in this order: [50, 30, 20, 40, 70, 60, 80], after deleting nodes 50, 30, and 20, how many nodes remain in the BST?

A 4

B 3

C 5

D 6

💡 Hint

Count nodes removed and remaining after each deletion carefully.

Initially 7 nodes. Deleting 50 removes one node, deleting 30 removes one node, deleting 20 removes one node. Total removed: 3. Remaining nodes: 7 - 3 = 4.