BST Delete Operation in DSA C++ - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Find node to delete

↓

Node found?

No→Stop: Node not found

Yes↓

Check children count

↓

Delete

↓

Replace node data

↓

Delete inorder successor

↓

Done

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

Execution Sample

DSA C++

DeleteNode(root, 20);

// Deletes node with value 20 from BST

This code deletes the node with value 20 from the BST, adjusting pointers to maintain BST properties.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	50	None	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ data:20│ │ data:40│ │ nextL:─┼──→ │ nextL:─┼──→ │ nextL:∅ │ │ nextL:∅ │ │ nextL:∅ │ │ nextR:─┼──→ │ nextR:─┼──→ │ nextR:─┼──→ │ nextR:∅ │ │ nextR:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head
2	Traverse left (20 < 50)	30	None	Same as step 1
3	Traverse left (20 < 30)	20	None	Same as step 1
4	Node found (20)	20	None	Same as step 1
5	Check children count (0 children)	20	None	Same as step 1
6	Delete node 20 (leaf)	20	Parent(30).nextL = null	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ data:40│ │ nextL:─┼──→ │ nextL:∅ │ │ nextL:∅ │ │ nextL:∅ │ │ nextR:─┼──→ │ nextR:─┼──→ │ nextR:∅ │ │ nextR:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
7	Done	null	None	Final tree without node 20

💡 Node 20 deleted as leaf node, parent pointer updated to null

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	Final
current	50	30	20	null	null
parent	null	50	30	30	30
root	50	50	50	50	50

Key Moments - 3 Insights

Why do we update parent.nextL to null when deleting node 20?

Because node 20 is a leaf with no children, we remove it by setting its parent's left pointer to null, as shown in step 6 of the execution_table.

What if the node to delete had one child?

We would replace the node with its single child by updating the parent's pointer to skip the node, similar to step 6 but pointing to the child instead of null.

Why do we traverse left when 20 < 50 and then 20 < 30?

Because in BST, smaller values go to the left subtree. The traversal steps 2 and 3 show moving left to find the node 20.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node at step 3?

A 50

B 30

C 20

D null

💡 Hint

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

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

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at 'Pointer Changes' column for when parent.nextL changes in execution_table

If node 20 had a right child, how would the pointer change in step 6?

A parent.nextL = null

B parent.nextL = node 20's right child

C parent.nextR = node 20's right child

D No pointer change

💡 Hint

Refer to key_moments about one child replacement and pointer updates

Concept Snapshot

BST Delete Operation:
- Find node to delete by BST property
- If leaf: remove by setting parent's pointer to null
- If one child: replace node with child
- If two children: replace with inorder successor
- Update pointers carefully to maintain BST
- Traversal follows left/right based on value

Full Transcript

The BST delete operation starts at the root and traverses left or right to find the node to delete. Once found, it checks the number of children. If the node is a leaf (no children), it is simply removed by setting the parent's pointer to null. If the node has one child, the parent's pointer is updated to point to that child, effectively removing the node. If the node has two children, the inorder successor is found, its value replaces the node's value, and then the successor node is deleted. This process maintains the BST properties. The execution table shows step-by-step traversal and pointer updates, especially how the parent's next pointer changes when deleting a leaf node. The variable tracker follows the current node and parent pointers during traversal and deletion.