BST Delete Operation in DSA Typescript - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Find node to delete

↓

Node found?

No→Stop: Node not found

Yes↓

Check node children

↓

No child

↓

Remove

↓

Replace node data

↓

Delete inorder successor

↓

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 Typescript

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

This code deletes a node with given key from BST by recursively finding it and handling cases of children.

Execution Table

Step	Operation	Node Visited	Action	Tree State (Inorder)
1	Start at root	50	Compare 50 with 50	[40, 50, 60, 70, 80]
2	Go left	40	Compare 40 with 60	[40, 50, 60, 70, 80]
3	Go right	60	Compare 60 with 40	[40, 50, 60, 70, 80]
4	Node found	60	Delete node 60 (no children)	[40, 50, 70, 80]
5	Update parent	50	Set right child of 50 to null	[40, 50, 70, 80]
6	Done	-	Return updated tree	[40, 50, 70, 80]

💡 Node 60 found with no children, deleted by setting parent's right pointer to null.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
currentNode	50	50	40	60	60	null	null
parentNode	null	50	40	40	40	40	40
root.left	40	40	40	40	40	40	40
root.right.left	60	60	60	60	null	null	null
root.right	70	70	70	70	70	70	70

Key Moments - 3 Insights

Why do we set the parent's right pointer to null after deleting node 60?

Because node 60 has no children, removing it means the parent's right pointer must no longer point to it, as shown in step 5 of the execution_table.

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 here but is part of the concept_flow.

Why do we compare key with current node data at each step?

To decide whether to go left or right in the BST, ensuring we find the node to delete efficiently, as seen in steps 1 to 3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the node visited at step 3?

A 60

B 70

C 50

D null

💡 Hint

Check the 'Node Visited' column at step 3 in the execution_table.

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

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where 'Set right child of 50 to null' happens in the Action column.

If node 60 had a right child, how would the deletion process change?

A Replace node 60 with its right child

B Delete node 60 without changes

C Replace node 60 with its left child

D Find inorder successor of node 50

💡 Hint

Refer to the concept_flow where one child case replaces node with its child.

Concept Snapshot

BST Delete Operation:
- Find node to delete by comparing keys
- If no children: remove node
- If one child: replace node with child
- If two children: replace with inorder successor
- Update pointers carefully to maintain BST
- Recursive approach simplifies traversal

Full Transcript

The BST delete operation starts at the root and searches for the node to delete by comparing the key with current node data. Once found, it handles three cases: if the node has no children, it is simply removed by updating the parent's pointer to null. If the node has one child, it is replaced by that child. If the node has two children, the inorder successor (smallest node in the right subtree) is found, its data replaces the node's data, and then the successor node is deleted. The execution table traces a deletion of node 60 which has no children, showing the traversal steps and pointer updates. The variable tracker shows how pointers and nodes change after each step. Key moments clarify why pointers are updated and how the traversal works. The visual quiz tests understanding of node visits, pointer updates, and deletion cases. The snapshot summarizes the key rules and steps for deleting nodes in a BST.