BST Delete Operation in DSA C++

Mental Model

Deleting a node in a BST means removing it while keeping the tree sorted. We find the node, then fix the tree by rearranging nodes if needed.

Analogy: Imagine removing a book from a sorted bookshelf. If the book is alone, just take it out. If it has neighbors, you might need to shift or replace it with a nearby book to keep order.

      5
     / \
    3   7
   / \   \
  2   4   8
↑root

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, delete node with value 3

Goal: Remove node 3 and keep BST property intact

Step 1: Find node with value 3 starting from root

      5
     / \
    [3] 7
   / \   \
  2   4   8

Why: We must locate the node to delete it

Step 2: Node 3 has two children, find its inorder successor (smallest in right subtree), which is 4

      5
     / \
    3   7
   / \   \
  2  [4]  8

Why: Inorder successor replaces node to keep BST order

Step 3: Replace node 3's value with 4

      5
     / \
    4   7
   / \   \
  2   4   8

Why: We copy successor's value to node to delete

Step 4: Delete original node 4 (successor), which has no left child

      5
     / \
    4   7
   /     \
  2       8

Why: Remove duplicate successor node, fixing tree

Result:

      5
     / \
    4   7
   /     \
  2       8

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

Node* findMin(Node* root) {
    while (root && root->left) {
        root = root->left; // advance to leftmost node
    }
    return root;
}

Node* deleteNode(Node* root, int key) {
    if (!root) return nullptr; // base case: empty tree

    if (key < root->val) {
        root->left = deleteNode(root->left, key); // go left to find key
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key); // go right to find key
    } else {
        // found node to delete
        if (!root->left) {
            Node* temp = root->right; // no left child, replace with right
            delete root;
            return temp;
        } else if (!root->right) {
            Node* temp = root->left; // no right child, replace with left
            delete root;
            return temp;
        } else {
            // two children: find inorder successor
            Node* temp = findMin(root->right); // smallest in right subtree
            root->val = temp->val; // copy successor value
            root->right = deleteNode(root->right, temp->val); // delete successor
        }
    }
    return root;
}

void inorderPrint(Node* root) {
    if (!root) return;
    inorderPrint(root->left);
    cout << root->val << " ";
    inorderPrint(root->right);
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(7);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->right = new Node(8);

    cout << "Original BST inorder: ";
    inorderPrint(root);
    cout << "\n";

    root = deleteNode(root, 3);

    cout << "BST inorder after deleting 3: ";
    inorderPrint(root);
    cout << "\n";

    return 0;
}

if (!root) return nullptr; // base case: empty tree

stop recursion if tree/subtree is empty

if (key < root->val) { root->left = deleteNode(root->left, key); // go left to find key }

search left subtree if key is smaller

else if (key > root->val) { root->right = deleteNode(root->right, key); // go right to find key }

search right subtree if key is larger

if (!root->left) { Node* temp = root->right; // no left child, replace with right delete root; return temp; }

delete node with no left child by replacing with right child

else if (!root->right) { Node* temp = root->left; // no right child, replace with left delete root; return temp; }

delete node with no right child by replacing with left child

Node* temp = findMin(root->right); // smallest in right subtree root->val = temp->val; // copy successor value root->right = deleteNode(root->right, temp->val); // delete successor

replace node with inorder successor and delete successor

Output

Original BST inorder: 2 3 4 5 7 8 

BST inorder after deleting 3: 2 4 5 7 8 

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root to node and possibly to successor

Space: O(h) due to recursion stack in worst case of skewed tree

vs Alternative: Compared to array deletion which may require shifting O(n), BST deletion is faster for balanced trees with O(log n) height

Edge Cases

Deleting a node not present in the tree

Function returns original tree unchanged

DSA C++

if (!root) return nullptr; // base case: empty tree

Deleting a leaf node (no children)

Node is simply removed and parent's pointer set to null

DSA C++

if (!root->left) { Node* temp = root->right; delete root; return temp; }

Deleting root node with two children

Root replaced by inorder successor and successor node deleted

DSA C++

Node* temp = findMin(root->right); root->val = temp->val; root->right = deleteNode(root->right, temp->val);

When to Use This Pattern

When asked to remove a node from a BST while keeping it sorted, use the BST delete operation pattern that handles three cases: no child, one child, and two children.

Common Mistakes

Mistake: Not handling the two children case by replacing with inorder successor
Fix: Implement logic to find inorder successor, copy its value, and delete successor node

Mistake: Deleting node without reconnecting child nodes properly
Fix: Return the correct child pointer after deletion to reconnect subtree

Summary

Deletes a node from a BST while maintaining the BST property.

Use when you need to remove a value from a BST and keep it sorted.

The key is to replace a node with two children by its inorder successor to keep order.