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.

Practice

1. What happens when you delete a leaf node (a node with no children) in a Binary Search Tree (BST)?

easy

A. The entire tree is rebuilt

B. The node is replaced by its right child

C. The node is replaced by its left child

D. The node is simply removed without affecting other nodes

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so deleting it means just removing it from the tree.

2. Step 2: Effect on the BST

   Since it has no children, no other nodes need to be moved or replaced.

3. Final Answer:

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

4. Quick Check:

   Leaf node deletion = simple removal [OK]

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

Common Mistakes:

• Thinking children need rearrangement
• Replacing leaf with child nodes
• Rebuilding the whole tree

2. Which of the following is the correct TypeScript function signature for deleting a node from a BST?

easy

A. function deleteNode(key: number): TreeNode

B. function deleteNode(root: number, key: TreeNode): void

C. function deleteNode(root: TreeNode | null, key: number): TreeNode | null

D. function deleteNode(root: TreeNode, key: string): TreeNode

Solution

1. Step 1: Analyze parameter types

   The root should be a TreeNode or null, and key should be a number to identify the node.

2. Step 2: Analyze return type

   The function returns the updated root node or null if tree becomes empty.

3. Final Answer:

   function deleteNode(root: TreeNode | null, key: number): TreeNode | null -> Option C

4. Quick Check:

   Correct parameter and return types = function deleteNode(root: TreeNode | null, key: number): TreeNode | null [OK]

Hint: Root can be null; key is number; returns updated root [OK]

Common Mistakes:

• Swapping parameter types
• Using wrong return type
• Using string instead of number for key

3. Given the BST below and the delete operation deleteNode(root, 10), what is the in-order traversal of the BST after deletion?

BST structure:
15
/ \
10 20
/ \ \
8 12 25

medium

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

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

C. [8, 15, 20, 25]

D. [12, 15, 20, 25]

Solution

1. Step 1: Delete node 10 with two children

   Node 10 has two children (8 and 12). Replace it with its inorder successor, which is 12.

2. Step 2: Remove node 12 from its original position

   After replacement, remove node 12 from right subtree of 10.

3. Step 3: In-order traversal after deletion

   Traversal is [8, 12, 15, 20, 25].

4. Final Answer:

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

5. Quick Check:

   Inorder after deleting 10 = [8, 12, 15, 20, 25] [OK]

Hint: Replace node with inorder successor for two children [OK]

Common Mistakes:

• Not replacing node 10 correctly
• Leaving node 10 in tree
• Incorrect traversal order

4. Consider this TypeScript code snippet for deleting a node from a BST. What is the bug?

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  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;
    deleteNode(root.right, minNode.val);
  }
  return root;
}

medium

A. No return statement after deletion

B. Missing assignment of root.right after deleting minNode

C. Wrong comparison operators for key

D. Incorrect base case for empty root

Solution

1. Step 1: Analyze deletion of minNode

   After copying minNode's value, the code calls deleteNode on root.right but does not assign the result back to root.right.

2. Step 2: Effect of missing assignment

   Without assignment, the minNode is not removed from the right subtree, causing duplicate values.

3. Final Answer:

   Missing assignment of root.right after deleting minNode -> Option B

4. Quick Check:

   Assign updated subtree after deletion [OK]

Hint: Always assign recursive delete result back to subtree [OK]

Common Mistakes:

• Forgetting to assign after recursive delete
• Misplacing base case
• Using wrong comparison signs

5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 30 (root). Which node becomes the new root after deletion using the standard BST delete operation?

hard

A. 35

B. 25

C. 40

D. 20

Solution

1. Step 1: Identify node 30's children

   Node 30 has two children: left subtree with 20 and right subtree with 40.

2. Step 2: Find inorder successor of 30

   Inorder successor is the smallest node in right subtree, which is 35.

3. Step 3: Replace 30 with 35 and delete 35 from right subtree

   35 replaces 30 as root, and 35 is removed from its original position.

4. Final Answer:

   35 -> Option A

5. Quick Check:

   Inorder successor replaces deleted node [OK]

Hint: Use inorder successor (smallest right subtree) for two-child node deletion [OK]

Common Mistakes:

• Using inorder predecessor instead
• Choosing wrong replacement node
• Not updating root after deletion