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.