BST Delete Operation in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a leaf node in BST

What is the printed state of the BST after deleting the leaf node with value 20?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

class BST {
    Node root;

    Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insert(root.left, val);
        else root.right = insert(root.right, val);
        return root;
    }

    Node delete(Node root, int val) {
        if (root == null) return null;
        if (val < root.val) root.left = delete(root.left, val);
        else if (val > root.val) root.right = delete(root.right, val);
        else {
            if (root.left == null && root.right == null) return null;
            else if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                Node succ = root.right;
                while (succ.left != null) succ = succ.left;
                root.val = succ.val;
                root.right = delete(root.right, succ.val);
            }
        }
        return root;
    }

    void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " -> ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        int[] vals = {50, 30, 70, 20, 40, 60, 80};
        for (int v : vals) tree.root = tree.insert(tree.root, v);
        tree.root = tree.delete(tree.root, 20);
        tree.inorder(tree.root);
        System.out.print("null");
    }
}

A 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

B 30 -> 40 -> 50 -> 60 -> 70 -> null

C 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

D 50 -> 30 -> 40 -> 60 -> 70 -> 80 -> null

💡 Hint

Deleting a leaf node removes it without affecting other nodes.

Deleting 20 removes the leaf node 20. The inorder traversal prints nodes in ascending order without 20.

❓ Predict Output

intermediate

Output after deleting a node with one child in BST

What is the printed state of the BST after deleting the node with value 30, which has one child?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

class BST {
    Node root;

    Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insert(root.left, val);
        else root.right = insert(root.right, val);
        return root;
    }

    Node delete(Node root, int val) {
        if (root == null) return null;
        if (val < root.val) root.left = delete(root.left, val);
        else if (val > root.val) root.right = delete(root.right, val);
        else {
            if (root.left == null && root.right == null) return null;
            else if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                Node succ = root.right;
                while (succ.left != null) succ = succ.left;
                root.val = succ.val;
                root.right = delete(root.right, succ.val);
            }
        }
        return root;
    }

    void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " -> ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        int[] vals = {50, 30, 70, 40, 60, 80};
        for (int v : vals) tree.root = tree.insert(tree.root, v);
        tree.root = tree.delete(tree.root, 30);
        tree.inorder(tree.root);
        System.out.print("null");
    }
}

A 50 -> 40 -> 60 -> 70 -> 80 -> null

B 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

C 40 -> 50 -> 60 -> 70 -> 80 -> null

D 40 -> 50 -> 60 -> 70 -> null

💡 Hint

Deleting a node with one child replaces it with its child.

Node 30 has one child 40. After deletion, 40 replaces 30. Inorder traversal reflects this.

❓ Predict Output

advanced

Output after deleting a node with two children in BST

What is the printed state of the BST after deleting the node with value 50, which has two children?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

class BST {
    Node root;

    Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insert(root.left, val);
        else root.right = insert(root.right, val);
        return root;
    }

    Node delete(Node root, int val) {
        if (root == null) return null;
        if (val < root.val) root.left = delete(root.left, val);
        else if (val > root.val) root.right = delete(root.right, val);
        else {
            if (root.left == null && root.right == null) return null;
            else if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                Node succ = root.right;
                while (succ.left != null) succ = succ.left;
                root.val = succ.val;
                root.right = delete(root.right, succ.val);
            }
        }
        return root;
    }

    void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " -> ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        int[] vals = {50, 30, 70, 20, 40, 60, 80};
        for (int v : vals) tree.root = tree.insert(tree.root, v);
        tree.root = tree.delete(tree.root, 50);
        tree.inorder(tree.root);
        System.out.print("null");
    }
}

A 20 -> 30 -> 40 -> 60 -> 70 -> 80 -> null

B 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

C 30 -> 40 -> 60 -> 70 -> 80 -> null

D 20 -> 30 -> 40 -> 60 -> 70 -> null

💡 Hint

Deleting a node with two children replaces it with its inorder successor.

Node 50 is replaced by its inorder successor 60. Then 60 is deleted from right subtree. Inorder traversal reflects this.

🔧 Debug

advanced

Identify the error in BST delete method

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

DSA Java

Node delete(Node root, int val) {
    if (root == null) return null;
    if (val < root.val) root.left = delete(root.left, val);
    else if (val > root.val) root.right = delete(root.right, val);
    else {
        if (root.left == null && root.right == null) return null;
        else if (root.left == null) return root.right;
        else if (root.right == null) return root.left;
        else {
            Node succ = root.right;
            while (succ.left != null) succ = succ.left;
            root.val = succ.val;
            // Missing recursive delete call here
        }
    }
    return root;
}

A StackOverflowError due to infinite recursion

B NullPointerException when accessing succ.left

C No error, code runs correctly

D The node with two children is not fully deleted, causing duplicate values

💡 Hint

Check if the inorder successor is removed after copying its value.

The code copies the inorder successor's value but does not delete the successor node from the right subtree, causing duplicate values in the BST.

🧠 Conceptual

expert

Minimum number of nodes in BST after deleting root with two children

Given a BST with 7 nodes, if the root node (which has two children) is deleted using the standard BST delete operation, how many nodes remain in the BST?

A 7

B 6

C 5

D Depends on the tree structure

💡 Hint

Deleting a node removes exactly one node from the tree.

Deleting the root node removes one node. The inorder successor replaces the root's value and is then deleted from its original position, so total nodes decrease by one.

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 simply removed and its parent's pointer is set to null.

B. The entire tree is restructured to maintain balance.

C. The node is replaced by its in-order predecessor.

D. The node is replaced by its in-order successor.

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: Effect on parent 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 A

4. Quick Check:

   Leaf node deletion = remove node and set parent's pointer null [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 predecessor or successor
• Confusing leaf node deletion with internal node deletion

2. Which of the following is the correct Java method signature for deleting a node with a given key from a BST?

easy

A. public boolean deleteNode(int key)

B. public void deleteNode(int key)

C. public int deleteNode(Node root, int key)

D. public Node deleteNode(Node root, int key)

Solution

1. Step 1: Understand BST delete method signature

   The method usually takes the root node and the key to delete, returning the updated root.

2. Step 2: Match method signature

   public Node deleteNode(Node root, int key) matches: it takes Node root and int key, returns Node (updated root).

3. Final Answer:

   public Node deleteNode(Node root, int key) -> Option D

4. Quick Check:

   Delete method returns updated root node [OK]

Hint: Delete method returns updated root node after deletion [OK]

Common Mistakes:

• Using void return type instead of Node
• Not passing root node as parameter
• Returning boolean or int instead of Node

3. Given the BST below, what is the in-order traversal after deleting the node with value 10?

       15
      /  \
    10    20
   /  \     \
  8   12    25

medium

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

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

C. [8, 12, 15, 20]

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

Solution

1. Step 1: Delete node 10 from BST

   Node 10 has two children (8 and 12). Replace it with its in-order successor (12) and delete 12.

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

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Replace deleted node with in-order successor for two children case [OK]

Common Mistakes:

• Not replacing node 10 correctly
• Including deleted node 10 in traversal
• Confusing in-order successor with predecessor

4. Consider this Java method snippet for deleting a node from a BST:

public Node deleteNode(Node root, int key) {
    if (root == null) 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 == null) return root.right;
        else if (root.right == null) return root.left;
        Node temp = minValueNode(root.right);
        root.val = temp.val;
        root.right = deleteNode(root.right, key);
    }
    return root;
}

private Node minValueNode(Node node) {
    Node current = node;
    while (current.left != null) current = current.left;
    return current;
}

What is the bug in this code?

medium

A. The recursive call to deleteNode uses key instead of temp.val.

B. The method does not handle the case when root is null.

C. The method minValueNode should return the maximum value node instead.

D. The method does not update root.left or root.right correctly.

Solution

1. Step 1: Analyze recursive delete call after replacement

   After replacing root.val with temp.val (in-order successor), the successor must be deleted from the right subtree using temp.val.

2. Step 2: Identify the bug

   The recursive call uses key (original value) instead of temp.val. Since key < values in right subtree, it won't correctly delete the successor.

3. Step 3: Check other options

   A is wrong (minValueNode finds successor correctly). B is wrong (null root handled). D is wrong (updates via recursion).

4. Final Answer:

   The recursive call to deleteNode uses key instead of temp.val. -> Option A

5. Quick Check:

   Recursive call must use temp.val [OK]

Hint: Check recursive calls carefully for correct key usage [OK]

Common Mistakes:

• Thinking minValueNode should find max value
• Confusing key and temp.val in recursive call
• Missing base case for null root

5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 20. Which of the following is the correct BST in-order traversal after deletion?

hard

A. [10, 25, 30, 40, 50]

B. [10, 20, 25, 30, 35, 40, 50]

C. [10, 25, 30, 35, 40, 50]

D. [25, 30, 35, 40, 50]

Solution

1. Step 1: Identify node 20's children

   Node 20 has two children: 10 (left) and 25 (right).

2. Step 2: Delete node 20 by replacing with in-order successor

   In-order successor is 25. Replace 20 with 25, then delete node 25.

3. Step 3: Perform in-order traversal

   Traversal order: 10, 25, 30, 35, 40, 50.

4. Final Answer:

   [10, 25, 30, 35, 40, 50] -> Option C

5. Quick Check:

   In-order after deleting 20 = [10, 25, 30, 35, 40, 50] [OK]

Hint: Replace deleted node with in-order successor for two children case [OK]

Common Mistakes:

• Leaving deleted node 20 in traversal
• Removing in-order successor node incorrectly
• Confusing in-order predecessor with successor