Delete Node in a BST

Problem

You are given the root of a Binary Search Tree (BST) and a value key. Delete the node whose value equals key, if it exists, and return the root of the resulting tree. The tree must remain a valid BST after the deletion.

Recall the BST property: every left descendant is smaller than a node and every right descendant is larger. Deleting a node with two children requires replacing it with a value that preserves this ordering.

If key is not in the tree, return the tree unchanged.

Examples

Example 1

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

Node 3 has two children (2 and 4). Replace 3 with its in-order successor 4 (the smallest value larger than 3), then remove that successor from its old spot.

Example 2

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]

There is no node with value 0, so the tree is returned unchanged.

Example 3

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

Node 6 has only a right child 7, so 6 is replaced by 7.

Constraints

• The number of nodes is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• Each node has a unique value.
• -10^5 <= key <= 10^5

Think about it first

TL;DR

Recursively locate the node, then handle 0/1/2-child cases — replacing a two-child node with its in-order successor — O(h) time, O(h) space.

Approach 1 — Recursive delete with successor replacement

Rebuilding the tree from a filtered value list would destroy its shape and cost O(n log n), so there is no useful brute force. Walk straight to the node using the BST property and handle three cases.

Deletion splits into three shapes. A leaf (no children) is removed by returning None. A node with one child is removed by returning that child, which slots into the parent’s link. A node with two children cannot just be dropped: replace its value with its in-order successor (the smallest value in the right subtree, larger than everything on the left and smaller than everything else on the right), then delete that successor, which by construction has at most one child.

flowchart TD
    subgraph before["Before: delete 3"]
        A5["5"] --> A3["3 (target)"]
        A5 --> A6["6"]
        A3 --> A2["2"]
        A3 --> A4["4 (successor)"]
        A6 --> A7["7"]
    end
    subgraph after["After"]
        B5["5"] --> B4["4"]
        B5 --> B6["6"]
        B4 --> B2["2"]
        B6 --> B7["7"]
    end
    before --> after

# 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

from typing import Optional


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

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # Found the node to delete.
        if not root.left:
            return root.right  # 0 or 1 (right) child
        if not root.right:
            return root.left  # 1 (left) child
        # Two children: find in-order successor (min of right subtree).
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = deleteNode(root.right, succ.val)

    return root

Walkthrough on Example 1 (root = [5,3,6,2,4,null,7], key = 3):

1. At 5: 3 < 5 → recurse left, will reassign 5.left.
2. At 3: match. It has two children (2 and 4).
3. Find successor = min of right subtree rooted at 4 → 4 (it has no left child).
4. Overwrite: 3.val = 4. Node is now 4.
5. Delete 4 from the right subtree: deleteNode(node(4), 4) matches at 4, which is a leaf → returns None, so the node’s right child becomes None.
6. The subtree is now 4 with left child 2, right child None. Back up, 5.left = this subtree.
7. Result [5,4,6,2,null,null,7].

Complexity: O(h) time — one downward path to find the node, plus at most one more path to find/delete the successor. O(h) space for the recursion stack (h = height; O(n) worst case, O(log n) balanced).

Approach 2 — In-order predecessor variant

The two-child case is symmetric: you can equally replace the node with its in-order predecessor, the largest value in the left subtree, then delete that predecessor from the left. Both keep the BST valid. The choice is stylistic, or used to balance which side shrinks.

# 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

from typing import Optional


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

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Two children: use in-order predecessor (max of left subtree).
        pred = root.left
        while pred.right:
            pred = pred.right
        root.val = pred.val
        root.left = deleteNode(root.left, pred.val)

    return root

Walkthrough on Example 3 (key = 6): descend 5 → 6 (6 > 5). At 6: root.left is None, so return root.right = node 7. The parent link 5.right becomes 7. Result [5,3,7,2,4]. The one-child case never touches the predecessor logic.

Complexity: O(h) time, O(h) space — identical to Approach 1.

Common pitfalls

• Reattaching the recursive result: you must write root.left = deleteNode(root.left, key) (and likewise for the right). Calling deleteNode without assigning its return value loses the spliced subtree.
• Deleting the successor’s value, not re-deleting the whole key: after copying succ.val into root, recurse on the right subtree with succ.val — recursing with the original key would loop or fail since root.val changed.
• Successor with a right child: the in-order successor is the leftmost node of the right subtree; it has no left child but may have a right child. The recursive delete handles that via the one-child case, so do not assume it is a leaf.
• Empty tree / key absent: returning None at the base case and not matching means an absent key leaves the tree unchanged (Example 2).
• Updating the parent link when the root itself is deleted: because every branch returns a node (or None) that the caller reassigns, deleting the actual root correctly returns the new root — do not forget to return root at the end.

Pattern takeaway

BST mutation problems follow a “recurse to locate, then fix up on the way back” shape: use the ordering to descend in O(h), and let each call return the (possibly new) subtree root so the parent relinks it. For two-child deletion, swap in the in-order successor or predecessor — the unique neighbouring value that preserves the sorted invariant — reducing the hard case to an easy one.