BST Insertion and Deletion

# CHAPTER 9

BST Insertion and Deletion #

1. Introduction #

2. Learning Objectives #

• Trace the recursive path required to seamlessly insert a new leaf node into a BST.

• Execute the 3 specific architectural rules of BST Deletion.

• Understand the logic of finding the "Inorder Successor" to heal severed branches.

• Write robust, crash-proof insertion and deletion code logic.

3. BST Insertion Algorithm #

The Strategy:

1. 1. Compare the new value to the Root.

1. 2. If it is smaller, plunge into the Left Subtree. If larger, plunge into the Right Subtree.

1. 3. Keep plunging until you hit a NULL dead end.

1. 4. Synthesize the new Node in RAM and link the final parent pointer to it.

Trace Example (Insert 13):

      [10]
     /    \
   [5]    [15]
          /  \
        [12] [20]

• Compare 13 to 10. 13 > 10 $\rightarrow$ Go Right.

• Compare 13 to 15. 13 < 15 $\rightarrow$ Go Left.

• Compare 13 to 12. 13 > 12 $\rightarrow$ Go Right.

• Node 12 has no right child (NULL). Anchor the new node [13] here!

4. BST Deletion Algorithm #

Scenario 1: The Node is a Leaf (0 Children)

• *Action:* The easiest execution. Because it supports no underlying architecture, simply delete it from RAM and set its parent's pointer to NULL.

Scenario 2: The Node has Exactly 1 Child

• *Action:* The "Bypass" maneuver. Delete the target node, and take its singular child branch and directly link it to the target node's parent. (Like a grandparent legally adopting a grandchild after the parent vanishes).

Scenario 3: The Node has Exactly 2 Children (The Nightmare Scenario)

• *Action:* You cannot delete it directly! If you delete the Root, you are left with two massive, disconnected Left and Right subtrees. You must find a mathematically perfect "Replacement Node" to slide into the severed position that respects all BST < and > constraints.

• The Solution: Find the Inorder Successor.

• The Inorder Successor is mathematically defined as the *absolute smallest node in the Right Subtree*.

• To find it: Go right one step, then aggressively plunge all the way down to the extreme Left Leaf.

• Copy the value of that Successor into the doomed node's spot.

• Finally, securely delete that original Successor leaf from the bottom of the tree.

5. Step-by-Step Scenario 3 Trace #

        [10] (DOOMED)
       /    \
     [5]    [15]
    /  \    /  \
  [2]  [7] [12] [20]

1. 1. Identify 10 has two children. Do NOT delete the physical pointers.

1. 2. Find the Inorder Successor (Smallest node in the Right Subtree).

1. 3. Jump right to [15]. Plunge extreme left to [12]. The Successor is 12.

1. 4. Overwrite the doomed node's data. (Change [10] to [12]).

1. 5. Now, safely delete the original [12] leaf node from the bottom using Scenario 1 rules.

6. Code Execution: Insertion #

def insert_bst(node, val):
    # Base Case: Hit a NULL slot, spawn the new Node
    if node is None:
        return Node(val)
        
    # Recursively traverse left or right
    if val < node.val:
        node.left = insert_bst(node.left, val)
    elif val > node.val:
        node.right = insert_bst(node.right, val)
        
    # Return the unchanged node pointer to re-stitch the tree
    return node 

7. Complexity Analysis #

• Time Complexity (Insert/Delete): $O(\log N)$ in a balanced tree, because the algorithm simply plunges straight down a singular branch. It degrades to horrific $O(N)$ if the tree is degenerate.

• Space Complexity: $O(1)$ Iterative, $O(\log N)$ Recursive stack.

8. Common Mistakes #

• Incorrectly linking the Inorder Successor: When developers extract the Inorder Successor, they often forget that the successor might have a *Right Child* of its own (Scenario 2). You must execute proper Scenario 2 bypass deletion on the successor, you cannot just blindly delete it!

9. Exercises #

1. 1. Draw the resulting visual tree after inserting the sequence [50, 30, 70, 20, 40] into an empty BST.

1. 2. In that generated tree, detail the precise structural pointer changes required to delete node 30.

10. MCQs with Answers #

11. Interview Preparation #

• *Algorithmic Edge Cases:* "When resolving a Two-Child deletion using the Inorder Successor, is it mathematically possible for that Successor node to *also* have Two Children, trapping you in an infinite recursion?" *(Answer: No! The Inorder Successor is structurally discovered by plunging extreme Left. If it had a Left Child, it wouldn't be the Successor! Therefore, the Successor mathematically guarantees it has either 0 or 1 Right Child, easily resolved by base deletion cases!)*

12. Summary #

13. Next Chapter Recommendation #