Delete Node in a BST

Delete Node in a BST

1. What is this problem about?

The Delete Node in a BST interview question is one of the most fundamental operations in tree management. Given a Binary Search Tree (BST) and a key, you must remove the node with that key while maintaining the BST property (left subtree < node < right subtree). This Delete Node in a BST coding problem is significantly harder than deletion in a simple binary tree because of the reorganization required after the node is gone.

2. Why is this asked in interviews?

Tech giants like Meta, Google, and Amazon ask this to verify if you understand the structural constraints of a Binary Search Tree interview pattern. It tests your ability to handle multiple cases: deleting a leaf, deleting a node with one child, and the complex case of deleting a node with two children.

3. Algorithmic pattern used

This problem uses Recursive Tree Search and Node Replacement.

• First, find the node using standard BST search logic.
• If the node is a leaf, just remove it.
• If it has one child, replace the node with that child.
• If it has two children, find the "In-order Successor" (the smallest value in the right subtree) or "In-order Predecessor," replace the target node's value with it, and then recursively delete that successor/predecessor node.

4. Example explanation

Suppose we want to delete 5 from a BST where 5 is the root, 3 is the left child, and 7 is the right child. Node 7 has a left child 6.

1. Node 5 has two children.
2. We find the in-order successor by going to the right (7) and then as far left as possible (6).
3. Replace 5 with 6.
4. Now delete the original node 6 from the right subtree. The new tree has 6 at the root, with 3 on the left and 7 on the right.

5. Common mistakes candidates make

• Breaking the BST property: Simply moving a child up without properly re-linking the entire subtree.
• Inefficient Search: Not utilizing the BST property to find the node in $O(\log N)$ time.
• Complex Successor Logic: Failing to correctly identify and delete the in-order successor, which can lead to duplicate nodes or broken pointers.

6. Interview preparation tip

Understand the three cases of BST deletion perfectly. The "two children" case is the most important—remember that replacing the value and then deleting the successor is the cleanest way to maintain tree balance and logic.