BST Delete Operation in DSA Java - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Compare key with current node

↓

Key < node

↓

Go left

↓

Found node to delete?

↓

No

↓

Return

↓

No child

↓

Remove

↓

Replace data and delete successor

↓

Return updated tree

The delete operation in a BST searches for the node, then deletes it based on its children count: no child, one child, or two children with inorder successor replacement.

Execution Sample

DSA Java

class Node {
  int data;
  Node left, right;
}

Node delete(Node root, int key) {
  // delete logic
}

Deletes a node with given key from BST and returns updated root.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	50	head points to 50	┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ head
2	Compare key=30 with 50, go left	50	current moves to left child 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ head current
3	Found node 30 to delete (no children)	30	parent.left set to null	┌────────┐ ┌────────┐ │ data:50│ │ data:70│ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ └────────┘ └────────┘ head
4	Return updated tree	50	head unchanged	┌────────┐ ┌────────┐ │ data:50│ │ data:70│ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ └────────┘ └────────┘ head

💡 Node with key 30 deleted; no children case handled by removing reference from parent.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
head	Node(50)	Node(50)	Node(50)	Node(50)
current	Node(50)	Node(30)	Node(30)	null (deleted)
parent.left	Node(30)	Node(30)	null	null

Key Moments - 3 Insights

Why do we need to keep track of the parent node during deletion?

Because when deleting a node, we must update the parent's pointer to remove or replace the deleted node, as shown in step 3 where parent.left changes from Node(30) to null.

What happens if the node to delete has two children?

We find the inorder successor (smallest node in right subtree), replace the node's data with it, then delete the successor node. This is not shown in this example but is part of the flow after step 3.

Why does the traversal stop when current node matches the key?

Because we found the node to delete, so we proceed to deletion steps instead of continuing traversal, as shown at step 3.

Visual Quiz - 3 Questions

Look at the execution table at step 2, which node does 'current' point to?

A Node with data 30

B Node with data 50

C Node with data 70

D null

💡 Hint

Check the 'Pointer Changes' and 'Node Visited' columns at step 2 in the execution table.

At which step is the parent's pointer updated to remove the deleted node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for 'parent.left set to null' in the 'Pointer Changes' column.

If the node to delete had one child, how would the 'Pointer Changes' differ at step 3?

A Parent pointer would be set to null

B Parent pointer would be set to the child node

C No pointer changes needed

D Root would be deleted

💡 Hint

Recall that for one child, parent's pointer links directly to the child node replacing the deleted node.

Concept Snapshot

BST Delete Operation:
- Search node by comparing key
- If no child: remove node
- If one child: link parent to child
- If two children: replace with inorder successor
- Update pointers carefully to maintain BST
- Return updated root after deletion

Full Transcript

The BST delete operation starts at the root and compares the key to find the node to delete. If the key is less, it goes left; if more, it goes right. When the node is found, deletion depends on children count: no children means simply remove the node by updating the parent's pointer to null; one child means link the parent directly to the child; two children means find the inorder successor, replace the node's data, then delete the successor. The execution table shows a simple case deleting node 30 with no children, updating the parent's left pointer to null. Variables track the current node and parent's pointers. Key moments clarify why parent tracking is needed and how traversal stops at the node. The visual quiz tests understanding of pointer changes and traversal steps.

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