BST Delete Operation in DSA C++ - Build from Scratch

BST Delete Operation

📖 Scenario: You are managing a simple phone book stored as a Binary Search Tree (BST). Each node contains a unique phone number. You want to be able to remove a phone number from this phone book.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a phone number to delete, performs the delete operation on the BST, and prints the BST in sorted order after deletion.

📋 What You'll Learn

Create a BST by inserting given phone numbers in order

Create a variable to hold the phone number to delete

Implement the BST delete operation for the given phone number

Print the BST nodes in ascending order after deletion

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find, add, or remove records like phone numbers.

💼 Career

Understanding BST delete operations is important for software engineers working with data storage, search algorithms, and system design.

1

Create BST with given phone numbers

Create a struct called Node with an int data, and Node* pointers left and right. Then create a function insertNode that takes Node* root and int data and inserts the data into the BST. Finally, create a Node* root and insert these phone numbers in this order: 50, 30, 70, 20, 40, 60, 80.

DSA C++

// Define Node struct
// Define insertNode function
// Create root and insert 50, 30, 70, 20, 40, 60, 80
// Your code here

Hint

Start by defining the Node structure with data and pointers. Then write the insertNode function to add nodes correctly. Finally, insert the given numbers into the BST.

2

Set the phone number to delete

Create an int variable called key and set it to 30. This is the phone number you want to delete from the BST.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* insertNode(Node* root, int data) {
    if (root == nullptr) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    if (data data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    // Create int variable key and set to 30
    // Your code here

    return 0;
}

Hint

Just create an integer variable named key and assign it the value 30.

3

Implement BST delete operation

Write a function Node* deleteNode(Node* root, int key) that deletes the node with value key from the BST and returns the new root. Use the standard BST delete logic: if the node has two children, replace it with its inorder successor (smallest node in right subtree). Then, in main, update root by calling deleteNode(root, key).

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* insertNode(Node* root, int data) {
    if (root == nullptr) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    if (data data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

// Add deleteNode function here

int main() {
    Node* root = nullptr;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    int key = 30;

    // Call deleteNode and update root
    // Your code here

    return 0;
}

Hint

Write the deleteNode function using recursion. Handle three cases: no child, one child, and two children. Use a helper function minValueNode to find the smallest node in the right subtree.

4

Print BST in sorted order after deletion

Write a function void inorder(Node* root) that prints the BST nodes in ascending order separated by spaces. Then call inorder(root) in main after deleting the node.

DSA C++

#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* insertNode(Node* root, int data) {
    if (root == nullptr) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    if (data data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

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

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

// Add inorder function here

int main() {
    Node* root = nullptr;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    int key = 30;

    root = deleteNode(root, key);

    // Call inorder(root) to print
    // Your code here

    return 0;
}

Hint

Use inorder traversal to print nodes in ascending order. Call inorder(root) after deletion and print a space after each node.

Practice

1. What happens when you delete a leaf node (a node with no children) from a Binary Search Tree (BST)?

easy

A. The node is replaced by its right child.

B. The entire tree is restructured to maintain BST properties.

C. The node is simply removed and its parent's pointer is set to null.

D. The node is replaced by its left child.

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so removing it does not affect other nodes.

2. Step 2: Update parent's pointer

   The parent's pointer to this node is set to null, effectively removing the node.

3. Final Answer:

   The node is simply removed and its parent's pointer is set to null. -> Option C

4. Quick Check:

   Leaf node deletion = remove node and nullify parent's pointer [OK]

Hint: Leaf node deletion just removes the node, no restructuring needed [OK]

Common Mistakes:

• Thinking the tree needs full restructuring
• Replacing leaf node with children when none exist
• Confusing leaf node deletion with internal node deletion

2. Which of the following is the correct syntax to delete a node with value key from a BST using a recursive function named deleteNode in C++?

easy

A. root.deleteNode(key);

B. deleteNode(root, key);

C. deleteNode(key, root);

D. root = deleteNode(root, key);

Solution

1. Step 1: Understand function signature

   The function returns the new root after deletion, so assignment is needed.

2. Step 2: Correct function call

   Calling root = deleteNode(root, key); updates the root pointer correctly.

3. Final Answer:

   root = deleteNode(root, key); -> Option D

4. Quick Check:

   Assign returned root after deletion [OK]

Hint: Always assign root = deleteNode(root, key) to update tree [OK]

Common Mistakes:

• Not assigning the returned root to update the tree
• Swapping argument order incorrectly
• Using method call syntax on root pointer

3. Consider the BST below and the code snippet that deletes the node with value 10:

    15
   /  \
  10  20
 /    / \
8    17 25

root = deleteNode(root, 10); What will be the in-order traversal of the BST after deletion?

medium

A. [8, 15, 10, 17, 20, 25]

B. [8, 15, 17, 20, 25]

C. [8, 15, 17, 20]

D. [8, 10, 15, 17, 20, 25]

Solution

1. Step 1: Identify node to delete and its children

   Node 10 has one child (8). Deleting 10 replaces it with 8.

2. Step 2: Perform in-order traversal after deletion

   In-order traversal visits nodes in ascending order: 8, 15, 17, 20, 25.

3. Final Answer:

   [8, 15, 17, 20, 25] -> Option B

4. Quick Check:

   In-order after deleting 10 = [8, 15, 17, 20, 25] [OK]

Hint: Replace deleted node with child or successor, then traverse in-order [OK]

Common Mistakes:

• Forgetting to replace node 10 with its child 8
• Including deleted node 10 in traversal
• Misordering nodes in traversal

4. The following C++ code attempts to delete a node from a BST but has a bug. What is the bug?

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) return root->right;
    else if (!root->right) return root->left;
    Node* temp = root->left; // BUG HERE
    root->val = temp->val;
    root->left = deleteNode(root->left, temp->val);
  }
  return root;
}

medium

A. It uses the left child instead of the inorder successor (right subtree minimum) for replacement.

B. It does not handle the case when root is null.

C. It deletes the wrong key by comparing incorrectly.

D. It does not update the root pointer after deletion.

Solution

1. Step 1: Identify replacement node for deletion

   For nodes with two children, the inorder successor (minimum in right subtree) should replace the node.

2. Step 2: Spot incorrect replacement

   The code incorrectly uses the left child as replacement, which breaks BST properties.

3. Final Answer:

   It uses the left child instead of the inorder successor (right subtree minimum) for replacement. -> Option A

4. Quick Check:

   Use inorder successor (right subtree min) for two-child deletion [OK]

Hint: Replace with inorder successor (min right subtree), not left child [OK]

Common Mistakes:

• Using left child instead of inorder successor
• Not updating pointers after replacement
• Ignoring null root check

5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 30 (root). Which node replaces the root to maintain BST properties?

hard

A. Node 35 (minimum node in right subtree)

B. Node 25 (maximum node in left subtree)

C. Node 40 (right child of root)

D. Node 20 (left child of root)

Solution

1. Step 1: Identify node to delete and its children

   Node 30 is root with two children: left subtree (20) and right subtree (40).

2. Step 2: Find inorder successor to replace root

   Inorder successor is the minimum node in right subtree, which is 35.

3. Step 3: Replace root with inorder successor

   Node 35 replaces 30 to maintain BST properties after deletion.

4. Final Answer:

   Node 35 (minimum node in right subtree) -> Option A

5. Quick Check:

   Root replacement = inorder successor (min right subtree) [OK]

Hint: Replace deleted root with inorder successor (min right subtree) [OK]

Common Mistakes:

• Replacing with left subtree max instead of right subtree min
• Replacing with direct child without checking subtree
• Confusing inorder predecessor and successor