title: Delete Node in a BST
slug: delete-node-in-a-bst
difficulty: medium
leetcode_id: 450
leetcode_url: https://leetcode.com/problems/delete-node-in-a-bst/
categories:
  - trees
patterns:
  - slug: tree-traversal
    is_optimal: true
  - slug: dfs
    is_optimal: false

function_signature: "def delete_node(root: TreeNode | None, key: int) -> TreeNode | None:"

test_cases:
  visible:
    - input: { root: [5, 3, 6, 2, 4, null, 7], key: 3 }
      expected: [5, 4, 6, 2, null, null, 7]
    - input: { root: [5, 3, 6, 2, 4, null, 7], key: 0 }
      expected: [5, 3, 6, 2, 4, null, 7]
    - input: { root: [], key: 0 }
      expected: []
  hidden:
    - input: { root: [5], key: 5 }
      expected: []
    - input: { root: [5, 3, 7], key: 5 }
      expected: [7, 3]
    - input: { root: [5, 3, 7, 2, 4, 6, 8], key: 3 }
      expected: [5, 4, 7, 2, null, 6, 8]
    - input: { root: [5, 3, 7, 2, 4, 6, 8], key: 7 }
      expected: [5, 3, 8, 2, 4, 6]
    - input: { root: [2, 1, 3], key: 1 }
      expected: [2, null, 3]
    - input: { root: [50, 30, 70, 20, 40, 60, 80], key: 50 }
      expected: [60, 30, 70, 20, 40, null, 80]

description: |
  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.

constraints: |
  - `0 <= number of nodes <= 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`

examples:
  - 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]. Another valid answer is [5,2,6,null,4,null,7]."
  - 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, so the tree remains unchanged."
  - input: "root = [], key = 0"
    output: "[]"
    explanation: "The tree is empty, so there is nothing to delete."

explanation:
  intuition: |
    Think of a BST like a filing cabinet organised alphabetically. When you want to remove a folder, you first need to **find it** using the BST property (smaller values go left, larger go right), and then **reorganise** the remaining folders to maintain the alphabetical order.

    The tricky part is the reorganisation. When deleting a node, there are three cases to consider:

    - **Leaf node (no children):** Simply remove it — no reorganisation needed
    - **One child:** Replace the deleted node with its only child — the BST property is preserved
    - **Two children:** This is the interesting case. You need to find a replacement that keeps the BST valid

    For the two-children case, the key insight is to use the **in-order successor** (the smallest node in the right subtree) or the **in-order predecessor** (the largest node in the left subtree). These are the only values that can replace the deleted node while maintaining the BST property.

    Why does the in-order successor work? It's the smallest value greater than the deleted node, so it's larger than everything in the left subtree but smaller than everything else in the right subtree — exactly what we need for a valid BST.

  approach: |
    We solve this using **recursive BST traversal** with three deletion cases:

    **Step 1: Search for the node to delete**

    - If `root` is `None`, return `None` (key not found)
    - If `key < root.val`, recursively search in the left subtree
    - If `key > root.val`, recursively search in the right subtree
    - If `key == root.val`, we've found the node to delete

    &nbsp;

    **Step 2: Handle the three deletion cases**

    - **Case 1 (No left child):** Return the right child to replace this node
    - **Case 2 (No right child):** Return the left child to replace this node
    - **Case 3 (Two children):** Find the in-order successor (minimum in right subtree), copy its value to the current node, then recursively delete the successor from the right subtree

    &nbsp;

    **Step 3: Return the modified tree**

    - Each recursive call returns the root of the modified subtree
    - Parent nodes automatically get updated through the recursive returns

    &nbsp;

    The recursive approach naturally handles the BST search and the parent-child reconnection without needing explicit parent pointers.

  common_pitfalls:
    - title: Forgetting to Handle the Two-Children Case
      description: |
        When a node has two children, you cannot simply remove it or replace it with one child. Both subtrees must remain in the result.

        The solution is to find the in-order successor (or predecessor), copy its value to the current node, and then delete the successor. This effectively "moves" the successor's value up while removing the actual successor node (which has at most one child).
      wrong_approach: "Trying to directly remove a node with two children"
      correct_approach: "Replace with in-order successor/predecessor, then delete that node"

    - title: Not Returning the Modified Subtree
      description: |
        A common mistake is to not properly return the modified subtree back up the recursion chain. Each recursive call should return the root of the (possibly modified) subtree.

        For example, when deleting a leaf node, returning `None` tells the parent to disconnect that child.
      wrong_approach: "Modifying nodes without returning the new subtree root"
      correct_approach: "Always return the root of the modified subtree from each recursive call"

    - title: Incorrect In-Order Successor Finding
      description: |
        The in-order successor is the **smallest** node in the right subtree, found by going right once, then left as far as possible.

        A common mistake is to confuse this with the largest node in the left subtree (which is the in-order predecessor — also valid, but different).
      wrong_approach: "Going right repeatedly or confusing successor with predecessor"
      correct_approach: "Go right once, then left until reaching a node with no left child"

  key_takeaways:
    - "**BST property enables O(h) search**: Use comparisons to navigate directly to the target node without checking every node"
    - "**Recursive structure simplifies parent updates**: By returning the modified subtree, parent-child links update automatically"
    - "**In-order successor/predecessor for two-children case**: These are the only valid replacements that maintain BST ordering"
    - "**Foundation for self-balancing trees**: Understanding BST deletion is essential for AVL trees, Red-Black trees, and other balanced structures"

  time_complexity: "O(h) where h is the height of the tree. In the worst case (skewed tree), this is O(n). In a balanced BST, this is O(log n)."
  space_complexity: "O(h) for the recursion stack. In the worst case O(n), in a balanced tree O(log n)."

solutions:
  - approach_name: Recursive BST Deletion
    is_optimal: true
    code: |
      class TreeNode:
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right

      def deleteNode(root: TreeNode | None, key: int) -> TreeNode | None:
          if not root:
              # Base case: key not found
              return None

          if key < root.val:
              # Key is in the left subtree
              root.left = deleteNode(root.left, key)
          elif key > root.val:
              # Key is in the right subtree
              root.right = deleteNode(root.right, key)
          else:
              # Found the node to delete
              if not root.left:
                  # Case 1: No left child, return right child
                  return root.right
              if not root.right:
                  # Case 2: No right child, return left child
                  return root.left

              # Case 3: Two children - find in-order successor
              # (smallest node in right subtree)
              successor = root.right
              while successor.left:
                  successor = successor.left

              # Copy successor's value to current node
              root.val = successor.val

              # Delete the successor from right subtree
              root.right = deleteNode(root.right, successor.val)

          return root
    explanation: |
      **Time Complexity:** O(h) — We traverse at most the height of the tree to find the node, plus potentially another O(h) to find and delete the successor.

      **Space Complexity:** O(h) — Recursion stack depth equals the height of the tree.

      This approach uses the BST property to efficiently find the node, then handles each deletion case appropriately. The recursive structure elegantly handles parent-child reconnection.

  - approach_name: Iterative Approach
    is_optimal: false
    code: |
      def deleteNode(root: TreeNode | None, key: int) -> TreeNode | None:
          if not root:
              return None

          # Find the node and its parent
          parent = None
          current = root

          while current and current.val != key:
              parent = current
              if key < current.val:
                  current = current.left
              else:
                  current = current.right

          # Key not found
          if not current:
              return root

          # Helper to find minimum in a subtree
          def find_min(node):
              while node.left:
                  node = node.left
              return node

          # Get the replacement node
          if not current.left:
              replacement = current.right
          elif not current.right:
              replacement = current.left
          else:
              # Two children: find successor and swap
              successor = find_min(current.right)
              current.val = successor.val
              # Recursively delete successor (has at most one child)
              current.right = deleteNode(current.right, successor.val)
              return root

          # Connect replacement to parent
          if not parent:
              return replacement
          if parent.left == current:
              parent.left = replacement
          else:
              parent.right = replacement

          return root
    explanation: |
      **Time Complexity:** O(h) — Same as recursive approach.

      **Space Complexity:** O(1) for the search phase, but still O(h) in worst case due to the recursive call for two-children case.

      This iterative approach explicitly tracks the parent node during traversal. While it avoids some recursion, the two-children case still benefits from recursion for simplicity. A fully iterative solution is possible but more complex.
