Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Given a binary search tree and a key, remove the node whose value equals the key and return the tree’s root. If the key is absent, the tree should remain unchanged. Every value is unique, so the binary-search-tree ordering identifies at most one node to delete.

Finding the node is the familiar part: compare the key with the current value and follow only the left or right child. The interesting part is repairing the tree after the node is found. Deletion has three structural cases:

  • A leaf can simply be disconnected.
  • A node with one child can be replaced by that child.
  • A node with two children needs a replacement value that keeps both subtrees in order.

The first two cases are direct. The third becomes manageable once the replacement is chosen carefully.

Deriving the optimal solution

For a node with two children, choose its inorder successor: the smallest node in its right subtree. That successor is found by moving once to the right and then as far left as possible.

This node is safe to promote for two reasons. Every value in the original left subtree is smaller than the node being deleted, and therefore smaller than the successor. Meanwhile, the successor is the smallest value in the right subtree, so no remaining value there belongs before it. Copying the successor’s value into the target position preserves the binary-search-tree ordering.

There is one more useful observation: the successor cannot have a left child, because it was chosen as the leftmost node. Removing it is therefore one of the easy cases. Its parent can point directly to the successor’s right child, if that child exists.

An iterative implementation can perform both the initial search and this repair while retaining only parent pointers. That gives O(h) time and O(1) auxiliary space, where h is the tree height. In a balanced tree, h is O(log n); in a completely skewed tree, it can be O(n).

Why the rewiring is correct

Before the target is found, each comparison discards the subtree that cannot contain the key, exactly as in ordinary BST search. If the search reaches None, the key is absent and returning the original root is correct.

If the target has at most one child, replacing it with that child preserves every relevant ordering relationship: the replacement subtree was already valid and already belonged entirely on the correct side of the target’s parent.

If the target has two children, its inorder successor is greater than every value in the target’s left subtree and no greater than any other value in its right subtree. After the successor’s value is copied, removing the old successor position preserves order because that node has no left child; its right child, if present, is still smaller than the successor’s former parent and can take its place. Thus all three deletion cases produce a valid BST containing exactly the original values except for the requested key.

Python solution

from __future__ import annotations

from typing import Optional


# LeetCode provides this class.
# class TreeNode:
#     def __init__(
#         self,
#         val: int = 0,
#         left: Optional[TreeNode] = None,
#         right: Optional[TreeNode] = None,
#     ) -> None:
#         self.val = val
#         self.left = left
#         self.right = right


class BinarySearchTreeDeletion:
    """Delete one value from a binary search tree in constant extra space."""

    @classmethod
    def delete(
        cls,
        root: Optional[TreeNode],
        key: int,
    ) -> Optional[TreeNode]:
        """Remove key if present and return the possibly changed root."""
        parent: Optional[TreeNode] = None
        target = root

        # Use BST ordering to locate the target and its parent.
        while target is not None and target.val != key:
            parent = target
            if key < target.val:
                target = target.left
            else:
                target = target.right

        if target is None:
            return root

        replacement = cls._delete_subtree_root(target)

        # Deleting the original root is the only case without a parent link
        # to repair.
        if parent is None:
            return replacement

        if parent.left is target:
            parent.left = replacement
        else:
            parent.right = replacement

        return root

    @staticmethod
    def _delete_subtree_root(target: TreeNode) -> Optional[TreeNode]:
        """Delete target and return the root of its repaired subtree."""
        if target.left is None:
            return target.right
        if target.right is None:
            return target.left

        # For two children, replace the target's value with the smallest
        # value in its right subtree, then unlink that successor node.
        successor_parent = target
        successor = target.right
        while successor.left is not None:
            successor_parent = successor
            successor = successor.left

        target.val = successor.val

        if successor_parent is target:
            # The right child itself was the successor.
            successor_parent.right = successor.right
        else:
            successor_parent.left = successor.right

        return target


class Solution:
    """LeetCode-compatible entry point."""

    def deleteNode(
        self,
        root: Optional[TreeNode],
        key: int,
    ) -> Optional[TreeNode]:
        return BinarySearchTreeDeletion.delete(root, key)

Interview follow-ups

How would a recursive solution work?

Each call compares the key with the current value and recursively updates either node.left or node.right. When the matching node is reached, the same zero-child, one-child, and two-child cases apply. For two children, the method finds the inorder successor, copies its value, and recursively deletes that value from the right subtree.

This closely mirrors the definition of a BST and is often the simplest solution to explain. It still takes O(h) time, but its call stack uses O(h) space. That is normally acceptable for a balanced tree, yet a skewed tree with thousands of nodes can exceed Python’s recursion limit; the iterative version avoids that failure mode.

Could the inorder predecessor be used instead?

Yes. The predecessor is the largest node in the left subtree: move left once, then follow right children. Its value can replace the target’s value, after which its left child, if any, is connected to its former parent.

The correctness argument and O(h) time, O(1) auxiliary-space bounds are symmetric to the successor approach. Choosing between them does not change the asymptotic cost. In a mutable tree, an implementation might select the taller side deliberately to reduce local structural disruption, although that alone does not make an ordinary BST balanced.

What if callers depend on node identity and values must not be copied?

The implementation should transplant the successor node itself rather than copying successor.val. First detach the successor from its old position. Then attach the target’s left subtree to the successor, attach the appropriate right subtree, and connect the target’s parent to the successor. Special care is needed when the successor is the target’s immediate right child so that links are not made cyclic.

The operation remains O(h) time and can remain O(1) in auxiliary space with tracked parents. The code is more intricate, but object identity is preserved for every surviving node—important when external structures retain node references or nodes contain immutable keys plus additional payload.

How does deletion change in a self-balancing search tree?

The initial BST deletion is still required, but it is followed by rebalancing on the path back toward the root. An AVL tree updates heights and performs rotations wherever balance factors leave the allowed range. A red-black tree instead repairs color and black-height violations with recoloring and rotations.

Those structures guarantee height O(log n), so search, deletion, and repair all take O(log n) worst-case time. The tradeoff is extra metadata and substantially more complex update logic. A plain BST keeps deletion simpler but offers only O(n) worst-case time when insertion order makes it skewed.

What if duplicate keys are allowed?

The data structure first needs an explicit duplicate policy. One option stores a multiplicity count in each node; deleting a key decrements the count and performs structural deletion only when the count reaches zero. This retains one node per distinct key and keeps the operation at O(h) time.

Another option stores duplicates as separate nodes consistently on one chosen side. Deleting “a key” can still remove the first matching node in O(h), but deleting a particular duplicate requires an identity or secondary key. The successor argument must also use the tree’s exact inequality convention, and duplicate-heavy data can produce poor height unless the tree is balanced.

How would deletion work in an immutable or persistent BST?

Instead of changing pointers in existing nodes, copy every node on the search path and reuse untouched subtrees. At the deletion point, return the surviving child or construct a replacement around the successor. Each older root continues to describe the old version, while the newly returned root describes the version after deletion.

Only O(h) new nodes are required because subtrees outside the affected paths are shared. Time is still O(h), but auxiliary space rises from O(1) to O(h). The benefit is safe versioning and simpler concurrent reads; the costs are allocation pressure and the need to keep node contents immutable.

What if every node stores subtree size for order-statistic queries?

Every ancestor whose subtree changed must have its size recomputed after deletion. A recursive solution naturally performs those updates while returning from calls. An iterative solution can store the affected path in a stack and update it in reverse order, using O(h) extra space, or rely on parent pointers already stored in the nodes.

Search and deletion remain O(h), and rank or k-th-smallest queries also take O(h). The tradeoff is stricter bookkeeping: rotations, successor removal, and every other structural change must update sizes correctly, or later order-statistic results become invalid.