# LeetCode 450: Delete Node in a BST

## Problem Restatement

We are given the root of a binary search tree and an integer `key`.

We need to delete the node whose value equals `key`.

After deletion, the tree must still be a valid binary search tree.

Return the possibly updated root of the tree.

The root can change. For example, if we delete the original root, some other node may become the new root.

The official problem describes the task in two stages: first search for the node, then delete it if it exists. If the key is absent, the tree remains unchanged.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root` of a BST and integer `key` |
| Output | Root of the updated BST |
| If key exists | Delete that node |
| If key does not exist | Return the original tree |
| BST rule | Left subtree values are smaller, right subtree values are larger |

The node class is usually:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

## Examples

Example 1:

```python
root = [5, 3, 6, 2, 4, None, 7]
key = 3
```

The tree is:

```text
        5
       / \
      3   6
     / \   \
    2   4   7
```

After deleting `3`, one valid result is:

```text
        5
       / \
      4   6
     /     \
    2       7
```

Output:

```python
[5, 4, 6, 2, None, None, 7]
```

Other valid BST shapes may also be accepted, as long as the node is deleted and the BST property remains valid.

Example 2:

```python
root = [5, 3, 6, 2, 4, None, 7]
key = 0
```

The key does not exist.

The tree is unchanged.

Example 3:

```python
root = []
key = 0
```

The answer is:

```python
None
```

## First Thought: Search Like a BST

To find the node, we use the BST property.

At a node:

| Condition | Action |
|---|---|
| `key < node.val` | Search left |
| `key > node.val` | Search right |
| `key == node.val` | Delete this node |

This avoids scanning the whole tree when the tree is balanced.

The harder part is deletion.

## Key Insight

Deleting a BST node has three cases.

| Case | Replacement |
|---|---|
| No left child | Return right child |
| No right child | Return left child |
| Two children | Replace with inorder successor |

The first two cases are simple.

If a node has no left child, its right child can take its place.

If a node has no right child, its left child can take its place.

The two-child case needs care.

For a node with two children, a valid replacement is the inorder successor.

The inorder successor is the smallest node in the right subtree.

It is found by starting at:

```python
root.right
```

then moving left until no left child remains.

This node is larger than every value in the left subtree and smaller than or equal to every value in the right subtree, so it can replace the deleted node while preserving the BST property.

## Algorithm

Define:

```python
deleteNode(root, key)
```

If `root` is `None`, return `None`.

If:

```python
key < root.val
```

delete from the left subtree:

```python
root.left = deleteNode(root.left, key)
```

If:

```python
key > root.val
```

delete from the right subtree:

```python
root.right = deleteNode(root.right, key)
```

Otherwise, `root.val == key`, so delete this node.

If one child is missing:

```python
if not root.left:
    return root.right

if not root.right:
    return root.left
```

If both children exist:

1. Find the smallest node in the right subtree.
2. Copy its value into `root`.
3. Delete that successor node from the right subtree.
4. Return `root`.

## Correctness

The recursive search follows the BST property.

If `key < root.val`, the key can only appear in the left subtree, so modifying only `root.left` preserves the right subtree unchanged.

If `key > root.val`, the key can only appear in the right subtree, so modifying only `root.right` preserves the left subtree unchanged.

When the node is found, the deletion cases preserve the BST property.

If the node has no left child, returning the right child is valid because every node in that right subtree is larger than the deleted node and still fits in the deleted node’s position.

If the node has no right child, returning the left child is valid because every node in that left subtree is smaller than the deleted node and still fits in the deleted node’s position.

If the node has two children, the inorder successor is the smallest value in the right subtree. It is larger than every value in the left subtree and no larger than the remaining values in the right subtree. Replacing the deleted node’s value with the successor value keeps the BST ordering valid.

The successor is then deleted from the right subtree, so no duplicate node remains.

Therefore, the returned tree contains all original values except `key`, and it remains a valid BST.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(h)` | Search and successor lookup follow one root-to-leaf path |
| Space | `O(h)` | Recursion stack height |

Here, `h` is the height of the BST.

For a balanced tree, `h = O(log n)`.

For a skewed tree, `h = O(n)`.

## Implementation

```python
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)
            return root

        if key > root.val:
            root.right = self.deleteNode(root.right, key)
            return root

        if not root.left:
            return root.right

        if not root.right:
            return root.left

        successor = self._min_node(root.right)
        root.val = successor.val
        root.right = self.deleteNode(root.right, successor.val)

        return root

    def _min_node(self, node: 'TreeNode') -> 'TreeNode':
        while node.left:
            node = node.left

        return node
```

## Code Explanation

The base case handles an empty subtree:

```python
if not root:
    return None
```

If the key is smaller, we delete from the left subtree:

```python
root.left = self.deleteNode(root.left, key)
```

If the key is larger, we delete from the right subtree:

```python
root.right = self.deleteNode(root.right, key)
```

When `root.val == key`, this is the node to delete.

If the node has no left child:

```python
return root.right
```

If the node has no right child:

```python
return root.left
```

These two cases also cover leaf deletion, because a leaf has both children missing.

For the two-child case, we find the inorder successor:

```python
successor = self._min_node(root.right)
```

Then copy its value:

```python
root.val = successor.val
```

Now the current node has the correct replacement value, but the successor node still exists in the right subtree. So we delete it:

```python
root.right = self.deleteNode(root.right, successor.val)
```

The helper finds the smallest node in a subtree:

```python
while node.left:
    node = node.left
```

## Testing

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root):
    if not root:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def run_tests():
    s = Solution()

    root = TreeNode(
        5,
        TreeNode(3, TreeNode(2), TreeNode(4)),
        TreeNode(6, None, TreeNode(7)),
    )

    root = s.deleteNode(root, 3)
    assert inorder(root) == [2, 4, 5, 6, 7]

    root = TreeNode(
        5,
        TreeNode(3, TreeNode(2), TreeNode(4)),
        TreeNode(6, None, TreeNode(7)),
    )

    root = s.deleteNode(root, 0)
    assert inorder(root) == [2, 3, 4, 5, 6, 7]

    root = TreeNode(1)
    root = s.deleteNode(root, 1)
    assert root is None

    root = TreeNode(2, TreeNode(1), None)
    root = s.deleteNode(root, 2)
    assert inorder(root) == [1]

    root = TreeNode(2, None, TreeNode(3))
    root = s.deleteNode(root, 2)
    assert inorder(root) == [3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Delete node with two children | Checks successor replacement |
| Missing key | Tree should remain unchanged |
| Delete only node | Returns `None` |
| Delete root with left child only | Promotes left child |
| Delete root with right child only | Promotes right child |