Delete Node in a BST
Given the root of a BST and a key, delete the node with the given key while maintaining the BST properties. Discuss the three cases for deletion (leaf, one child, two children).
Why Interviewers Ask This
Amazon asks this to evaluate a candidate's mastery of tree recursion and edge-case handling under pressure. They specifically test if you understand BST invariants while managing complex pointer manipulations. The question reveals your ability to decompose a multi-step logic problem into distinct cases, ensuring structural integrity without excessive memory usage.
How to Answer This Question
1. Clarify requirements: Confirm input validation and whether the key is guaranteed to exist. 2. Outline the strategy: State that you will search for the node first, then handle deletion based on its children count. 3. Define the three scenarios: Leaf nodes (remove directly), one child (replace with child), and two children (find inorder successor/predecessor). 4. Discuss complexity: Mention O(h) time where h is height and O(1) space for iterative or O(h) for recursive stack. 5. Walk through an example: Trace the logic with a specific tree structure before writing code to ensure clarity.
Key Points to Cover
- Explicitly distinguishing between the three deletion scenarios (leaf, single child, two children)
- Correctly identifying and implementing the inorder successor logic for nodes with two children
- Maintaining strict adherence to BST properties after every modification
- Demonstrating awareness of time complexity relative to tree height rather than just N
- Handling edge cases such as deleting the root node or empty trees gracefully
Sample Answer
To delete a node in a Binary Search Tree while maintaining properties, I first locate the target node using standard BST search logic. Once found, I handle three distinct cases. First, if the node is a leaf, I simply ret…
Common Mistakes to Avoid
- Attempting to swap pointers incorrectly, which breaks the tree structure or creates cycles
- Forgetting to update the parent's reference when removing a non-root node
- Choosing the wrong successor (e.g., max of left subtree instead of min of right) causing order violations
- Neglecting to discuss base cases or recursion termination conditions in the explanation
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.