BST Delete Operation in DSA Javascript - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Find node to delete

↓

Node found?

No→Stop: Node not in tree

Yes↓

Check node children

↓

No child

↓

Remove node

↓

Replace node data with successor

↓

Delete successor node recursively

↓

Done

The delete operation in a BST first finds the node, then handles three cases: no child, one child, or two children, adjusting pointers accordingly.

Execution Sample

DSA Javascript

function deleteNode(root, key) {
  if (!root) return null;
  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;
    if (!root.right) return root.left;
    let minNode = findMin(root.right);
    root.val = minNode.val;
    root.right = deleteNode(root.right, minNode.val);
  }
  return root;
}

function findMin(node) {
  while (node.left) {
    node = node.left;
  }
  return node;
}

Deletes a node with given key from BST by recursively finding it and handling three cases.

Execution Table

Step	Operation	Node Visited	Action	Tree State (Inorder)
1	Start at root	50	Compare 50 with 30 (key)	10 → 20 → 30 → 40 → 50 → 60 → 70
2	Go left	30	Compare 30 with 30 (key)	10 → 20 → 30 → 40 → 50 → 60 → 70
3	Node found	30	Node to delete found	10 → 20 → 30 → 40 → 50 → 60 → 70
4	Check children	30	Node has two children	10 → 20 → 30 → 40 → 50 → 60 → 70
5	Find inorder successor	40	Find min in right subtree (40)	10 → 20 → 30 → 40 → 50 → 60 → 70
6	Replace node value	30	Replace 30 with 40	10 → 20 → 40 → 50 → 60 → 70
7	Delete successor node	40	Delete node 40 in right subtree	10 → 20 → 40 → 50 → 60 → 70
8	Successor node has no left child	40	Replace node 40 with its right child (null)	10 → 20 → 40 → 50 → 60 → 70
9	Return updated tree	50	Return root after deletion	10 → 20 → 40 → 50 → 60 → 70
10	End	null	Deletion complete	10 → 20 → 40 → 50 → 60 → 70

💡 Node with key 30 deleted; tree updated with inorder successor replacement.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 8	Final
root.val	50	50	50	50	50
current node	50	30	30 replaced by 40	40 deleted	50
inorder successor	null	null	40	40	null
left subtree	10 → 20 → 30 → 40	10 → 20 → 30 → 40	10 → 20 → 40	10 → 20 → 40	10 → 20 → 40
right subtree	50 → 60 → 70	50 → 60 → 70	50 → 60 → 70	50 → 60 → 70	50 → 60 → 70

Key Moments - 3 Insights

Why do we replace the node's value with the inorder successor's value instead of just deleting the node?

Because the node has two children, directly deleting it would break the BST property. Replacing its value with the inorder successor (smallest node in right subtree) keeps the BST valid. See execution_table steps 4-6.

What happens if the node to delete has only one child?

The node is replaced directly by its single child, maintaining the BST structure. This is simpler than the two-children case. This is implied in the code but not shown in this example.

Why do we delete the inorder successor node after copying its value?

Because the inorder successor node is moved up to replace the deleted node's value, we must remove the original successor node to avoid duplicates. See execution_table steps 7-8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the node value replaced with at step 6?

A 40

B 30

C 50

D 20

💡 Hint

Check the 'Action' column at step 6 in execution_table.

At which step does the algorithm find the inorder successor?

A Step 3

B Step 5

C Step 7

D Step 9

💡 Hint

Look for 'Find inorder successor' in the 'Operation' column.

If the node to delete had no children, what would happen in the execution_table?

A Node would be replaced by its right child

B Node would be replaced by its left child

C Node would be removed directly with no replacement

D Inorder successor would be found

💡 Hint

Recall the 'no child' case in concept_flow and key_moments.

Concept Snapshot

BST Delete Operation:
- Find node to delete by comparing keys
- If no child: remove node directly
- If one child: replace node with child
- If two children: replace node value with inorder successor
- Delete inorder successor node recursively
- Maintains BST property after deletion

Full Transcript

The BST delete operation starts at the root and searches for the node with the given key. Once found, it checks the number of children the node has. If the node has no children, it is simply removed. If it has one child, the node is replaced by that child. If it has two children, the node's value is replaced with the inorder successor's value (the smallest node in the right subtree), and then the inorder successor node is deleted recursively. This process maintains the binary search tree property. The execution table traces these steps with the node values and tree state after each operation.

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 without affecting other nodes.

B. The entire tree is rebuilt from scratch.

C. The node's children replace it in the tree.

D. The root node is always changed.

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 BST structure

   Since no children exist, simply remove the node and update its parent's pointer to null.

3. Final Answer:

   The node is simply removed without affecting other nodes. -> Option A

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal only [OK]

Common Mistakes:

• Thinking children replace the node when none exist
• Assuming root always changes
• Believing tree rebuild is needed

2. Which of the following is the correct syntax to delete a node with value key from a BST in JavaScript?

easy

A. bst.deleteNode(key);

B. bst.delete(key);

C. bst.remove(key);

D. bst.erase(key);

Solution

1. Step 1: Identify common BST delete method

   In many JavaScript BST implementations, the method to delete a node is named delete.

2. Step 2: Check method naming conventions

   Methods like remove, erase, or deleteNode are not standard or common in JavaScript BST examples.

3. Final Answer:

   bst.delete(key); -> Option B

4. Quick Check:

   Standard BST delete method = delete() [OK]

Hint: Use bst.delete(key) to remove nodes [OK]

Common Mistakes:

• Using remove() or erase() which are not standard
• Confusing delete keyword with method name
• Using deleteNode() which is uncommon

3. Consider this BST and the delete operation:

    10
   /  \
  5    15
       / \
      12  20

What will be the in-order traversal output after deleting node with value 15?

medium

A. [5, 10, 12, 15, 20]

B. [5, 10, 20]

C. [5, 10, 12, 20]

D. [5, 10, 15, 20]

Solution

1. Step 1: Identify node to delete and its children

   Node 15 has two children: 12 (left) and 20 (right).

2. Step 2: Replace node 15 with its in-order successor

   The in-order successor is the smallest node in right subtree, which is 20. Replace 15 with 20 and delete original 20 node.

3. Step 3: Perform in-order traversal

   In-order traversal visits nodes in ascending order: 5, 10, 12, 20.

4. Final Answer:

   [5, 10, 12, 20] -> Option C

5. Quick Check:

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

Hint: Replace deleted node with in-order successor [OK]

Common Mistakes:

• Removing 15 without replacement
• Using in-order predecessor instead of successor
• Forgetting to delete the successor node

4. The following code attempts to delete a node from a BST but causes an error. What is the main issue?

function deleteNode(root, key) {
  if (!root) return null;
  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;
    let minNode = findMin(root.right);
    root.val = minNode.val;
    // Missing deletion of minNode here
  }
  return root;
}

function findMin(node) {
  while (node.left) node = node.left;
  return node;
}

medium

A. The function does not handle leaf nodes correctly.

B. The base case for recursion is missing.

C. The function uses incorrect comparison operators.

D. The code does not delete the in-order successor node after copying its value.

Solution

1. Step 1: Analyze deletion of node with two children

   When deleting a node with two children, we replace its value with the in-order successor's value.

2. Step 2: Check if in-order successor node is deleted

   The code copies the successor's value but does not delete the successor node itself, causing duplicate values and incorrect tree.

3. Final Answer:

   The code does not delete the in-order successor node after copying its value. -> Option D

4. Quick Check:

   Must delete successor node after value copy [OK]

Hint: Always delete successor node after copying value [OK]

Common Mistakes:

• Forgetting to delete the in-order successor node
• Missing base case (though present here)
• Incorrectly handling leaf nodes
• Using wrong comparison operators

5. You have a BST with nodes: 8, 3, 10, 1, 6, 14, 4, 7, 13.
After deleting node 3, what is the correct in-order traversal of the BST?

hard

A. [1, 4, 6, 7, 8, 10, 13, 14]

B. [1, 3, 4, 6, 7, 8, 10, 13, 14]

C. [1, 6, 7, 8, 10, 13, 14]

D. [1, 4, 7, 8, 10, 13, 14]

Solution

1. Step 1: Identify node 3 and its children

   Node 3 has two children: 1 (left) and 6 (right). 6 has children 4 and 7.

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

   The in-order successor of 3 is 4 (smallest in right subtree). Replace 3 with 4, then delete original 4 node.

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

   In-order traversal visits nodes in ascending order: 1, 4, 6, 7, 8, 10, 13, 14.

4. Final Answer:

   [1, 4, 6, 7, 8, 10, 13, 14] -> Option A

5. Quick Check:

   In-order after deleting 3 = [1, 4, 6, 7, 8, 10, 13, 14] [OK]

Hint: Replace deleted node with in-order successor, then traverse [OK]

Common Mistakes:

• Forgetting to delete the in-order successor node
• Using in-order predecessor instead
• Skipping nodes in traversal