BST Deletion

Inserting into a BST always adds a new leaf, making insertion relatively simple. Deletion is harder because removing an internal node can leave a gap that breaks the left-less-right-greater rule unless the tree is rearranged carefully. There are three cases, depending on how many children the node being deleted has.

Case 1: deleting a leaf

This is the simplest case: remove the node, and nothing else needs to change.

Deleting 30:

Case 2: deleting a node with one child

Connect the node's parent directly to its only child, skipping over the deleted node. This is the same idea used when removing a middle node from a linked list.

Deleting 30, its only child 40 takes its place:

Case 3: deleting a node with two children

Inorder successor

Inorder of this tree: 20 30 40 50 60 70 80. The successor of 50 is the value right after it in that sequence: 60.

INORDER_SUCCESSOR(NODE)
 
1. CURRENT = NODE->right
2. While CURRENT->left != NULL:
       CURRENT = CURRENT->left
3. Return CURRENT   // smallest value in NODE's right subtree

INORDER_PREDECESSOR(NODE)
 
1. CURRENT = NODE->left
2. While CURRENT->right != NULL:
       CURRENT = CURRENT->right
3. Return CURRENT   // largest value in NODE's left subtree

Deleting with the inorder successor

Delete 50 from the tree above. Its successor is 60. Replace 50's value with 60:

Then delete the original 60 node from the right subtree. That node has at most one child, since a successor found by going right once and then left as far as possible can never have a left child of its own, otherwise it would not be the smallest value in the subtree. Its removal is therefore Case 1 or Case 2. The BST property still holds throughout: every value that was smaller than 50 is still smaller than 60, since 60 was the smallest value larger than 50 to begin with.

DELETE(ROOT, KEY)   // KEY is the value to delete from the tree rooted at ROOT
 
1. If ROOT == NULL:
       Return NULL
2. If KEY < ROOT->data:
       ROOT->left = DELETE(ROOT->left, KEY)
3. Else if KEY > ROOT->data:
       ROOT->right = DELETE(ROOT->right, KEY)
4. Else:
       If ROOT->left == NULL AND ROOT->right == NULL:   // Case 1: leaf
           free(ROOT)
           Return NULL
       If ROOT->left == NULL:                           // Case 2: only right child
           TEMP = ROOT->right
           free(ROOT)
           Return TEMP
       If ROOT->right == NULL:                          // Case 2: only left child
           TEMP = ROOT->left
           free(ROOT)
           Return TEMP
       Else:                                            // Case 3: two children
           TEMP = INORDER_SUCCESSOR(ROOT)
           ROOT->data = TEMP->data
           ROOT->right = DELETE(ROOT->right, TEMP->data)
5. Return ROOT.

KTU PYQ: Constructing and Deleting from a BST

Building the tree. Insert 35, 12, 47, 36, 52, 30, 25, 49 in order, starting from an empty tree.

Insert 35. Empty tree, becomes the root:

Insert 12. 12 < 35 → left of 35:

Insert 47. 47 > 35 → right of 35:

Insert 36. 36 > 35 → right (to 47); 36 < 47 → left of 47:

Insert 52. 52 > 35 → right (to 47); 52 > 47 → right of 47:

Insert 30. 30 < 35 → left (to 12); 30 > 12 → right of 12:

Insert 25. 25 < 35 → left (to 12); 25 > 12 → right (to 30); 25 < 30 → left of 30:

Insert 49. 49 > 35 → right (to 47); 49 > 47 → right (to 52); 49 < 52 → left of 52:

This is the final tree, with all eight values placed.

Delete 30. It has one child, 25, so this is Case 2: 25 takes 30's place.

Delete 47 using its inorder successor. 47 has two children, so this is Case 3. Its right subtree:

The smallest value there is 49 (go right to 52, then left to 49), so successor(47) = 49. Replace 47 with 49, then delete the original 49 node (a leaf, Case 1):

Quick recall

• Leaf: delete directly, no relinking needed.
• One child: connect the deleted node's parent directly to its only child.
• Two children: replace the node's value with its inorder successor (smallest in the right subtree) or inorder predecessor (largest in the left subtree), then delete that value from its original spot.
• The inorder successor of a node with a right subtree is found by going right once, then left as far as possible; it never has a left child of its own.
• Deletion complexity matches search and insertion: O(log n) balanced, O(n) worst case.