⚡Flashcard Drill➔
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

  1. Search for the key as in a normal BST descent.
  2. Once found, there are three cases: no left child (return the right), no right child (return the left), and two children.
  3. 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.
  4. 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 None for 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems