LeetCode 450: Delete Node in a BST Solution in Python – A Step-by-Step Guide

What Is LeetCode 450: Delete Node in a BST?

In LeetCode 450: Delete Node in a BST, you’re given a BST root and a key (value) to delete. Your task is to remove the node with that value and return the new root, ensuring the BST property holds: for any node, all left subtree values are less, and all right subtree values are greater. For example, deleting 3 from 5→3→7 might leave 5→7, but with more nodes, you’d replace with a successor or predecessor. It’s like performing tree surgery, excising a node and healing the structure.

Problem Statement

• Input: root (TreeNode)—BST root; key (int)—value to delete.
• Output: TreeNode—new root after deletion.
• Rules:
• BST property: left < node < right.
• Delete key if present, adjust tree accordingly.
• Return updated root.

Constraints

• Number of nodes: [0, 10^4].
• -10^5 <= node.val <= 10^5.
• Each node has a unique value.
• -10^5 <= key <= 10^5.

Examples to Get Us Started

• Input: root = [5,3,6,2,4,null,7], key = 3
• Output: [5,4,6,2,null,null,7] (3 replaced by 4).
• Input: root = [5,3,6,2,4,null,7], key = 0
• Output: [5,3,6,2,4,null,7] (0 not found).
• Input: root = [], key = 0
• Output: [] (Empty tree).

Understanding the Problem: Pruning the BST

To solve LeetCode 450: Delete Node in a BST in Python, we need to find and remove a node with the given key, then reconnect the tree while preserving BST properties. Deletion has three cases: no children (easy cut), one child (simple swap), or two children (replace with successor/predecessor). A naive approach—flattening to array and rebuilding—works but is O(n) space. We can do better with tree traversal. We’ll explore:

• Best Solution (Recursive Deletion): O(h) time, O(h) space—elegant and BST-friendly.
• Alternative Solution (Iterative Deletion): O(h) time, O(1) space—explicit and space-light.

Let’s dive into the recursive solution—it’s the surgeon’s scalpel we need.

Best Solution: Recursive Deletion with BST Property Maintenance

Why This Is the Best Solution

The recursive deletion approach is the top pick because it’s O(h) time (h = tree height) and O(h) space (recursion stack), leveraging BST’s ordered nature for a clean, intuitive solution. It finds the node, handles all cases recursively, and adjusts the tree with minimal fuss. It’s like a tree doctor making precise cuts, letting the BST heal itself through recursion—smooth and efficient!

How It Works

Here’s the strategy:

• Step 1: Search for key recursively:
• If key < root.val, recurse left.
• If key > root.val, recurse right.
• Step 2: Found the node (root.val = key):
• Case 1: No children—return None.
• Case 2: One child—return the child.
• Case 3: Two children—find min in right subtree (successor), replace value, delete successor.
• Step 3: Return updated root.
• Why It Works:
• BST order guides search.
• Successor maintains properties in two-child case.

Step-by-Step Example

Example: root = [5,3,6,2,4,null,7], key = 3

• Tree:

5 / \ 3 6 / \ \ 2 4 7

• Delete 3:
• Find 3 (left of 5).
• Two children (2, 4).
• Successor: min in right (4), no smaller in 4’s subtree.
• Replace 3 with 4, delete 4 (no children).
• Result:

5 / \ 4 6 / \ 2 7

• Output: [5,4,6,2,null,null,7].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy code# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None

        # Step 1: Search for key
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            # Step 2: Found the node to delete
            # Case 1: No children
            if not root.left and not root.right:
                return None
            # Case 2: One child
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            # Case 3: Two children
            # Find successor (min in right subtree)
            successor = root.right
            while successor.left:
                successor = successor.left
            root.val = successor.val
            # Delete successor
            root.right = self.deleteNode(root.right, successor.val)

        return root

• Line 11-12: Base case—empty tree.
• Line 14-16: Search:
• key < val: recurse left, update left link.
• key > val: recurse right, update right link.
• Line 17-31: Delete:
• No kids: return None.
• One kid: return the child.
• Two kids: find successor, copy value, delete successor recursively.
• Line 33: Return updated root.
• Time Complexity: O(h)—height traversal.
• Space Complexity: O(h)—recursion stack.

It’s like a BST pruning robot!

Alternative Solution: Iterative Deletion

Why an Alternative Approach?

The iterative deletion method avoids recursion—O(h) time, O(1) space—using pointers to manually traverse and adjust the tree. It’s more hands-on, like a surgeon working step-by-step with a scalpel, and uses less stack space. Good for explicit control or space constraints!

How It Works

• Step 1: Find node and its parent iteratively.
• Step 2: Delete based on cases:
• No children: cut link.
• One child: bypass node.
• Two children: find successor, replace, adjust links.
• Step 3: Return root.

Step-by-Step Example

Example: root = [5,3,6,2,4,null,7], key = 3

• Find:
• Root = 5, key < 5, go left.
• Node = 3, parent = 5.
• Delete:
• Two children: 2, 4.
• Successor: 4 (min in right).
• Replace 3 with 4, 4 has no left, link 2 as left child.
• Result: [5,4,6,2,null,null,7].

Code for Iterative Approach

Copy codeclass Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None

        # Find node and parent
        parent = None
        curr = root
        while curr and curr.val != key:
            parent = curr
            if key < curr.val:
                curr = curr.left
            else:
                curr = curr.right

        # Key not found
        if not curr:
            return root

        # Delete based on cases
        if not curr.left and not curr.right:  # No children
            if curr == root:
                return None
            if parent.left == curr:
                parent.left = None
            else:
                parent.right = None
        elif not curr.left or not curr.right:  # One child
            child = curr.left if curr.left else curr.right
            if curr == root:
                return child
            if parent.left == curr:
                parent.left = child
            else:
                parent.right = child
        else:  # Two children
            # Find successor
            succ_parent = curr
            succ = curr.right
            while succ.left:
                succ_parent = succ
                succ = succ.left
            curr.val = succ.val
            # Delete successor
            if succ_parent.left == succ:
                succ_parent.left = succ.right
            else:
                succ_parent.right = succ.right

        return root

• Time Complexity: O(h)—traversal to key and successor.
• Space Complexity: O(1)—no recursion.

It’s a manual BST trimmer!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(h), clean, intuitive.
• Cons: O(h) space.
• Iterative (Alternative):
• Pros: O(h), O(1) space, explicit.
• Cons: More code, less elegant.

Recursive wins for clarity.

Edge Cases and More Examples

• Input: [] → [].
• Input: [1], 1 → [].
• Input: [2,1,3], 2 → [3,1].

Recursive handles all smoothly.

Complexity Recap

• Recursive: Time O(h), Space O(h).
• Iterative: Time O(h), Space O(1).

Recursive is the champ here.

Key Takeaways

• Recursive: Let BST heal itself.
• Iterative: Hands-on pruning.
• Python Tip: Recursion simplifies trees—see [Python Basics](/python/basics).

Final Thoughts: Prune That BST

LeetCode 450: Delete Node in a BST in Python is a tree surgery masterclass. Recursive deletion is your elegant scalpel, while iterative offers a manual touch. Want more BST action? Try LeetCode 701: Insert into a BST or LeetCode 98: Validate BST. Ready to snip some nodes? Head to Solve LeetCode 450 on LeetCode and trim that tree today—your coding skills are branching out!