> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Delete Node in a BST Python Solution

> Tested Python solution for LeetCode 450 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 450, Medium. Topics: Tree, Binary Search Tree, Binary Tree. [View on LeetCode](https://leetcode.com/problems/delete-node-in-a-bst/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 450   # by problem number
lcpy gen -s delete_node_in_a_bst   # by problem name
```

## Problem

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return *the **root node reference** (possibly updated) of the BST*.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Note: When a node with two children is deleted, replacing it with either its inorder successor or predecessor is accepted.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg)

```
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: One valid answer is [5,4,6,2,null,null,7]; [5,2,6,null,4,null,7] is also accepted.
```

```
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.
```

```
Input: root = [], key = 0
Output: []
```

### Constraints

* The number of nodes in the tree is in the range \[0, 10^4].
* -10^5 \<= Node.val \<= 10^5
* Each node has a unique value.
* `root` is a valid binary search tree.
* -10^5 \<= key \<= 10^5

**Follow up:** Could you solve it with time complexity O(height of tree)?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/delete_node_in_a_bst/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/delete_node_in_a_bst/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from leetcode_py import TreeNode


class Solution:
    # Time: O(h) where h is the height of the tree
    # Space: O(h) recursion stack
    def delete_node(self, root: TreeNode[int] | None, key: int) -> TreeNode[int] | None:
        if root is None:
            return None

        if key < root.val:
            root.left = self.delete_node(root.left, key)
        elif key > root.val:
            root.right = self.delete_node(root.right, key)
        else:
            # Node found: handle deletion by child count.
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            # Two children: replace value with inorder successor, delete successor.
            successor = root.right
            while successor.left is not None:
                successor = successor.left
            root.val = successor.val
            root.right = self.delete_node(root.right, successor.val)
        return root
```

## Complexity

| Time                                   | Space                |
| -------------------------------------- | -------------------- |
| O(h) where h is the height of the tree | O(h) recursion stack |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).