The O(n) Club: Delete Node in a BST — When Trees Demand Therapy

The O(n) Club: Delete Node in a BST — When Trees Demand Therapy

⚡ TL;DR

Deleting a node in a BST is three things: drama-free for leaves, awkward handoffs for single-child nodes, and utterly Shakespearean if the node has two kids. Don’t just delete and pray—the BST insists on staying sorted or you’ll get haunted by phantom bugs. Here’s what rookies try:

// Brute force — leaves only!
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else root = null; // This breaks for non-leaves
    return root;
}

That works for leaves. But try it anywhere else, and your BST will file a bug report… against you.

🧠 How Devs Usually Mess This Up

What really goes wrong? Classic mistakes:

• Ignore the node’s children and just unplug; that breaks your tree family in half.
• Delete a node with two kids like it’s a regular one—then panic when nodes go missing or appear out of nowhere.
• Assume deletion is always O(1)—reality check: for unbalanced trees it’s as slow as a Monday morning.
• Forget that deleting the root can mean there’s a whole new root now (not just the same hash code with a combover).

🔍 What’s Actually Going On

Picture your BST as a team in an office. Remove an employee (node), and you have to shuffle the roles, but HR insists the hierarchy rules still apply. So:

• No children? Just fire them. Tree stays clean.
• One child? Promote the lone intern instantly. Minimal trauma (for you, anyway).
• Two children? Now comes the Game of Thrones arc. You have to find the inorder successor (the next bigger value in the right subtree), transfer them in as the new you, and then do the whole process again to quietly delete the successor. All while keeping the BST sorted—otherwise the search party gets lost forever.

Miss a step and your once-perfect BST is now a scary, unsorted LinkedIn connection graph.

🛠️ PseudoCode

• Traverse left or right recursively to find the target node.
• If you find it:
  • 🎈 If no children: return null (snip!)
  • 👶 If one child: return that child
  • 🔥 If two children:
    • Find inorder successor (leftmost right child)
    • Copy successor’s value to current node
    • Delete successor recursively from right subtree
• Always return the new root pointer after each recursion

// Pseudocode
if (root == null) 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 (no left) return right;
    if (no right) return left;
    successor = findMin(root.right);
    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val);
return root;

💻 The Code

// Definition for binary tree node
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // Node found!
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode successor = findMin(root.right);
        root.val = successor.val;
        root.right = deleteNode(root.right, successor.val);
    }
    return root;
}
 private TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Deleting the root? Assign the new root! Java won’t update your variable by magic.
• Still mixing up keys and nodes? Stop it—the function works by searching, not psychic pointers.
• Remember: Every recursion needs to return the new subtree root.
• Complexity: O(h) time/space (h = height). That’s O(log n) for happy, balanced trees; O(n) for sticks. Sorry.

🧠 Interviewer Brain-Tattoo

“Deleting from a BST: It’s like firing a manager who has two eager assistants. If you don’t pick the next in line, the org chart becomes fan fiction.”