# Delete Node in a BST
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-node-in-a-bst)
Canonical: https://scaleengineer.com/dsa/problems/delete-node-in-a-bst
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/delete-node-in-a-bst/image0.jpg) 

**Input:** root = [5,3,6,2,4,null,7], key = 3
**Output:** [5,4,6,2,null,null,7]
**Explanation:** Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
![](https://assets.glich.co/dsa/delete-node-in-a-bst/image1.jpg)

**Example 2:**

**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.

**Example 3:**

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

**Constraints:**

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

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

# Approaches
## Recursive Deletion
This approach utilizes recursion to traverse the Binary Search Tree. The function calls itself on the left or right subtree based on the comparison between the node's value and the key. Once the target node is found, it's deleted according to one of three cases: the node has no children, one child, or two children. The recursive structure elegantly handles the re-linking of nodes after deletion.
**Time:** O(H), where H is the height of the tree. In a balanced BST, H is approximately log(N), leading to O(log N) time. In the worst case of a skewed tree, H is N, leading to O(N) time. · **Space:** O(H) for the recursion call stack, where H is the height of the tree. In the worst case of a skewed tree, this can be O(N).
**Pros:** The code is clean, concise, and closely follows the recursive definition of a tree, making it easier to reason about.; Handles all deletion cases elegantly within a single function.
**Cons:** The recursive calls consume stack space, which can lead to a `StackOverflowError` for very deep trees (e.g., a skewed tree with many nodes).; Slightly higher overhead than an iterative solution due to function call mechanics.
### Explanation
The core of this method is a function `deleteNode(root, key)` that returns the root of the modified subtree.

*   **Base Case**: If the `root` is `null`, it means the key is not present in the tree, so we return `null`.

*   **Search Phase**:
    *   If the `key` is less than `root.val`, the node to be deleted lies in the left subtree. We make a recursive call: `root.left = deleteNode(root.left, key)`.
    *   If the `key` is greater than `root.val`, it must be in the right subtree. We recurse on the right: `root.right = deleteNode(root.right, key)`.

*   **Deletion Phase** (`key == root.val`):
    1.  **Node with 0 or 1 child**: If `root.left` is `null`, we can simply replace the current node with its right child (`root.right`). Similarly, if `root.right` is `null`, we replace it with `root.left`. This single check handles both the leaf node case (where both children are null) and the single-child case.
    2.  **Node with 2 children**: This is the complex case. To maintain the BST property, we must replace the node's value with its in-order successor (the smallest value in its right subtree). 
        *   Find the minimum node in the right subtree.
        *   Copy the successor's value to the current node (`root.val = successor.val`).
        *   Now, we must delete that successor node from the right subtree. We do this by making another recursive call: `root.right = deleteNode(root.right, root.val)`. Since the successor is the minimum element, it has at most one (right) child, so its deletion will fall into the simpler case (1).

The assignments `root.left = ...` and `root.right = ...` are crucial as they update the tree structure by connecting the parent node to the new root of the modified subtree.

```java
class Solution {
    /**
     * Finds the node with the minimum value in a given subtree.
     */
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        // Base case: if the tree is empty, return null.
        if (root == null) {
            return null;
        }

        // Recurse down the tree
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // Node to be deleted is found
            
            // Case 1 & 2: Node with one or no child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Case 3: Node with two children
            // Find the in-order successor (smallest in the right subtree)
            TreeNode successor = findMin(root.right);
            // Copy the successor's content to this node
            root.val = successor.val;
            // Delete the in-order successor from the right subtree
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
}
```
### Algorithm
- If `root` is null, return `null`.
- If `key < root.val`, recursively call delete on the left subtree: `root.left = deleteNode(root.left, key)`.
- If `key > root.val`, recursively call delete on the right subtree: `root.right = deleteNode(root.right, key)`.
- If `key == root.val`, the node is found. Handle the three deletion cases:
  - **Case 1 (0 or 1 child):** If `root.left` is null, return `root.right`. If `root.right` is null, return `root.left`.
  - **Case 2 (2 children):** Find the in-order successor (minimum node in the right subtree). Copy its value to the current node. Recursively delete the successor node from the right subtree.
- Return the `root`.

## Iterative Deletion
This approach uses a loop instead of recursion to find and delete the target node. By manually managing pointers to the current node and its parent, it avoids the overhead and stack depth limitations of recursion. While the logic is more involved, especially for the two-children case, it offers better space efficiency.
**Time:** O(H), where H is the height of the tree. The time complexity is dominated by the traversal to find the node and, in the worst case, another traversal to find the successor. For a balanced tree, this is O(log N); for a skewed tree, it's O(N). · **Space:** O(1). This approach uses a constant amount of extra space for pointers (`parent`, `current`, `successor`, etc.), regardless of the tree's size or shape.
**Pros:** Extremely space-efficient, using only O(1) extra space.; Avoids recursion depth limits and potential stack overflow errors, making it more robust for very large and deep trees.
**Cons:** The code is more complex and less intuitive than the recursive version.; Managing parent pointers and handling all edge cases (like deleting the root) manually can be error-prone.
### Explanation
The iterative solution involves two main steps: finding the node to delete and its parent, and then performing the deletion by re-wiring the parent's and children's pointers.

*   **Search Phase**:
    *   We use two pointers, `current` starting at `root` and `parent` starting at `null`.
    *   We traverse the tree in a `while` loop until `current` becomes `null` (key not found) or `current.val` equals the `key`.
    *   Inside the loop, we update `parent` to `current` before moving `current` to its left or right child.

*   **Deletion Phase**:
    *   If `current` is `null`, the key was not found, and we return the original `root`.
    *   The deletion logic is split into the same cases, but handled by direct pointer manipulation. A clever trick is to reduce the two-children case to the zero/one-child case.
    1.  **Node with 2 children**: If `current` has both a left and a right child, we find its in-order successor (the smallest node in the right subtree) and the successor's parent. We copy the successor's value to `current.val`. Then, instead of deleting the original `current` node, we mark the successor node for deletion. Since the successor has at most one child (a right child), this transforms the problem into the simpler case. We update `current` and `parent` to point to the successor and its parent, and let the logic for the next case handle the actual removal.
    2.  **Node with 0 or 1 child**: At this point, `current` is the node to be physically removed (either the original target or the successor from the previous step). We identify its single child (or `null` if it's a leaf). We then update the `parent`'s `left` or `right` pointer to bypass `current` and point directly to this `child`. A special check is needed if we are deleting the root node (`parent` is `null`), in which case the `child` becomes the new root of the tree.

```java
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode current = root;
        TreeNode parent = null;

        // Step 1: Find the node to delete and its parent.
        while (current != null && current.val != key) {
            parent = current;
            if (key < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        // If the key is not in the tree, return the original root.
        if (current == null) {
            return root;
        }

        // Step 2: The node to delete ('current') is found.
        
        // Case 3: Node with two children.
        // We reduce this to Case 1 or 2 by finding the in-order successor.
        if (current.left != null && current.right != null) {
            TreeNode successorParent = current;
            TreeNode successor = current.right;
            while (successor.left != null) {
                successorParent = successor;
                successor = successor.left;
            }
            
            // Copy the value of the successor to the current node.
            current.val = successor.val;
            
            // Now, the problem is to delete the successor node.
            // We update 'current' and 'parent' to point to the successor and its parent
            // and let the logic for Case 1/2 handle the deletion.
            current = successor;
            parent = successorParent;
        }

        // Step 3: Handle Case 1 (no child) and Case 2 (one child).
        // At this point, 'current' is the node to be physically removed,
        // and it has at most one child.
        TreeNode child = (current.left != null) ? current.left : current.right;

        // If we are deleting the root node.
        if (parent == null) {
            return child;
        }

        // If the node to be deleted is a left or right child.
        if (current == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }

        return root;
    }
}
```
### Algorithm
- Initialize `parent = null`, `current = root`.
- Loop to find the node to delete: while `current != null` and `current.val != key`, update `parent` and move `current` to the appropriate child.
- If `current` is `null` after the loop, the key was not found. Return `root`.
- **If `current` has two children:**
  - Find the in-order successor and its parent in the right subtree.
  - Copy the successor's value to `current`.
  - Update `current` and `parent` to be the successor and its parent, effectively marking the successor for deletion.
- **If `current` has zero or one child (this now includes the reduced two-child case):**
  - Identify the non-null child of `current` (or `null` if it's a leaf).
  - If `parent` is `null` (deleting the root), the new root is the child.
  - Otherwise, update `parent.left` or `parent.right` to point to the child, bypassing `current`.
- Return the `root` of the tree.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode deleteNode ( TreeNode root , int key ) { if ( root == null ) { return null ; } if ( root . val > key ) { root . left = deleteNode ( root . left , key ); return root ; } if ( root . val < key ) { root . right = deleteNode ( root . right , key ); return root ; } if ( root . left == null ) { return root . right ; } if ( root . right == null ) { return root . left ; } TreeNode node = root . right ; while ( node . left != null ) { node = node . left ; } node . left = root . left ; root = root . right ; return root ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * deleteNode ( TreeNode * root , int key ) { if ( ! root ) return root ; if ( root -> val > key ) { root -> left = deleteNode ( root -> left , key ); return root ; } if ( root -> val < key ) { root -> right = deleteNode ( root -> right , key ); return root ; } if ( ! root -> left ) return root -> right ; if ( ! root -> right ) return root -> left ; TreeNode * node = root -> right ; while ( node -> left ) node = node -> left ; node -> left = root -> left ; root = root -> right ; return root ; } };
```

### Python

```python
# 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 root is None : return None if root . val > key : root . left = self . deleteNode ( root . left , key ) return root if root . val < key : root . right = self . deleteNode ( root . right , key ) return root if root . left is None : return root . right if root . right is None : return root . left node = root . right while node . left : node = node . left node . left = root . left root = root . right return root
```