NeetCode #423LC-450MediumTreesNC 250
← Back to All Problems#423 · #450 · Delete Node in a BST(删除二叉搜索树中的节点)
📌 Problem Statement & Constraints
Given the root of a binary search tree and a key, delete the node with that key and return the root. The tree must remain a valid BST. Constraints: the number of nodes is in
[0, 10^4], -10^5 <= Node.val <= 10^5; values are unique.💡 Core Algorithmic Approaches
- Search for the key as in a normal BST descent.
- Once found, there are three cases: no left child (return the right), no right child (return the left), and two children.
- For two children, replace the node's value with its in-order successor (the leftmost node of the right subtree) and then delete that successor from the right subtree.
- Returning the (possibly new) subtree root from each call handles the relinking automatically.
💻 Benchmark Python3 Implementation
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
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:
# found the node to delete
if not root.left:
return root.right # no left child
if not root.right:
return root.left # no right child
# two children: replace with the in-order successor
succ = root.right
while succ.left:
succ = succ.left # leftmost of the right subtree
root.val = succ.val
root.right = self.deleteNode(root.right, succ.val)
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(h): the search plus the successor lookup each follow one path.
💾 Space Complexity
O(h) for the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Using the in-order predecessor instead: also correct, but pick one and be consistent -- the successor is the conventional choice.
- Forgetting to delete the successor after copying its value: the tree would contain a duplicate.
- Returning
Nonefor a node with one child: the existing child must be returned so the parent relinks correctly. - Deleting from the left subtree when the successor came from the right: the recursive delete must target
root.right.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.