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.

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