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 return null to detach it from its parent. Second, if it has only one child, I replace the node with that child, effectively bypassing the deleted node. The most complex case is when the node has two children. Here, I cannot simply remove it; I must preserve the BST order. I find the inorder successor, which is the smallest value in the right subtree. I copy this successor's value into the current node, then recursively delete the successor node from the right subtree. This ensures the left subtree remains smaller than the new root value and the right subtree remains larger. For Amazon's focus on ownership and precision, I would verify edge cases like deleting the root or handling duplicate keys if specified. Finally, I analyze the time complexity as O(h), where h is the tree height, and space complexity depends on the recursion stack depth.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
Find K Closest Elements (Heaps)
Medium
MetaEvaluate Reverse Polish Notation (Stack)
Medium
SpotifyConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDesign a Set with $O(1)$ `insert`, `remove`, and `check`
Easy
CiscoDesign a 'Trusted Buyer' Reputation Score for E-commerce
Medium
AmazonDesign a CDN Edge Caching Strategy
Medium
Amazon