Delete Node in a BST — LC 450 Interview Deep Dive

Problem Statement#

LeetCode 450 — Delete Node in a BST | Difficulty: Medium

Given the root of a Binary Search Tree and an integer key, delete the node with that key and return the updated root. The BST must remain valid after deletion.

Constraints:

• 0 <= number of nodes <= 10^4
• -10^5 <= Node.val <= 10^5
• Each node has a unique value
• -10^5 <= key <= 10^5

Input:  root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]

Input:  root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]

Why This Problem Matters#

BST deletion is one of the most frequently tested BST problems in FAANG interviews because it forces you to reason through all edge cases of a recursive data structure. Unlike insertion (which always adds a leaf) or search (read-only), deletion must preserve the BST invariant while potentially restructuring multiple nodes. Amazon, Google, and Microsoft commonly use this problem to test recursive thinking and tree manipulation skills.

The three-case structure of BST deletion is a pattern you will encounter again in AVL trees, red-black trees, and segment trees. Understanding it deeply unlocks a whole class of tree manipulation problems that appear at senior engineering levels.

The Core Insight#

BST deletion has exactly three cases, each with a clean solution:

1. Leaf node (no children): Simply remove it by returning null to the parent.
2. One child: Replace the node with its single child. The BST invariant holds because all values in that subtree were already in the correct relative position.
3. Two children: Find the in-order successor (the smallest value in the right subtree — the leftmost node of the right child). Copy that value into the current node, then delete the successor from the right subtree. The successor is guaranteed to have at most one child, so its deletion falls into case 1 or 2.

Key BST invariant to preserve: every node in the left subtree is smaller, every node in the right subtree is larger.

Visual Dry Run#

Delete key = 3 from the tree:

Result: [5,4,6,2,null,null,7] — BST invariant 2 < 4 < 5 < 6 < 7 confirmed.

Solution (Optimal)#

class Solution:
    def deleteNode(self, root, key):
        if not root:
            return None
 
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            # Case 1 and 2: zero or one child
            if not root.left:
                return root.right
            if not root.right:
                return root.left
 
            # Case 3: two children — find in-order successor
            successor = root.right
            while successor.left:
                successor = successor.left
 
            root.val = successor.val
            root.right = self.deleteNode(root.right, successor.val)
 
        return root

var deleteNode = function(root, key) {
    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 successor = root.right;
        while (successor.left) {
            successor = successor.left;
        }
 
        root.val = successor.val;
        root.right = deleteNode(root.right, successor.val);
    }
 
    return root;
};

Time: O(h) — h is tree height; O(log n) balanced, O(n) skewed Space: O(h) — recursion stack depth

Common Mistakes#

• Using the right child directly as the successor instead of the leftmost node of the right subtree
• Forgetting to recursively delete the successor after copying its value, leaving a duplicate
• Not returning root at the end of the recursive function
• Checking key != found but failing to handle the empty tree base case first
• Mixing in-order predecessor and successor logic inconsistently

Interview Tips#

• Always state the three cases before writing code — interviewers want to hear you enumerate them
• Mention that in-order predecessor (rightmost of left subtree) is equally valid
• Note that the recursive approach is cleaner than iterative with parent pointers
• For balanced BST variants (AVL, red-black), mention that rotation rebalancing follows deletion

Follow-up Questions#

• Can we use the in-order predecessor instead? Yes — rightmost node of left subtree. Both produce a valid BST.
• How do you delete by rank (k-th smallest)? Find the k-th smallest via in-order traversal, then call delete with that value.
• How does this change for AVL trees? Same core deletion, plus balance-factor checks and rotations on the way back up.
• Can this be done iteratively? Yes, but requires tracking a parent pointer. The recursive approach is preferred in interviews.
• What if there are duplicate values? Standard BSTs forbid duplicates; if allowed, deletion logic must specify "delete leftmost occurrence."

Key Takeaways#

• BST deletion has exactly three cases: leaf, one child, two children
• The two-children case uses the in-order successor (minimum of right subtree) to preserve the BST invariant
• After copying the successor value, you must delete the original successor node from the right subtree
• The successor has at most one child (a right child), so its deletion is always a simpler case
• Time complexity is O(h) where h = tree height — O(log n) for balanced, O(n) for skewed
• Returning the modified root at each recursive step is what "rewires" the tree without explicit parent pointers
• This pattern — reducing a complex case to a simpler recursive call — is fundamental to all recursive tree algorithms