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.