#450

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Delete Node in a BST

Delete Node in a BST hinges on removing one target while preserving in-order ordering through carefully chosen subtree replacement.

tree binary search tree binary tree

Problem Statement

You are given the root of a binary search tree and an integer key. Remove the node whose value equals key, if it exists, and return the possibly updated root. The result must still satisfy the BST rule that every left subtree value is smaller than the node and every right subtree value is larger.

The real challenge is not locating the node, but reconnecting the tree after deletion. A leaf can simply disappear, a node with one child can be bypassed, and a node with two children must be replaced with a value that keeps sorted in-order traversal intact. In the classic example root = [5,3,6,2,4,null,7] with key = 3, replacing 3 with 4 yields one valid output [5,4,6,2,null,null,7], though another structurally different valid BST can also be accepted.

Examples

Example 1

Input: root = [5,3,6,2,4,null,7], key = 3

Output: [5,4,6,2,null,null,7]

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.

Example 2

Input: root = [5,3,6,2,4,null,7], key = 0

Output: [5,3,6,2,4,null,7]

The tree does not contain a node with value = 0.

Example 3

Input: root = [], key = 0

Output: []

Example details omitted.

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

Solution Approach

Search by BST ordering until you find the deletion point

Use the BST property to move left when key is smaller than the current node and right when key is larger. This avoids scanning unrelated branches. Once the current node matches key, stop treating it like a search problem and switch to one of the three deletion cases, because this is where Delete Node in a BST is usually won or lost.

Handle zero-child and one-child nodes with direct relinking

If the matched node has no children, return null so the parent drops it. If it has exactly one child, return that child so the parent now points directly to the surviving subtree. This return-the-new-subtree-root pattern keeps parent updates simple, especially in recursive code where each call rebuilds its own left or right pointer.

For two children, replace with inorder successor, then delete that successor

When the node has both left and right children, choose the smallest value in the right subtree as the inorder successor. Copy that value into the current node, then recursively delete the successor from the right subtree. This keeps the BST ordering correct because the successor is the next larger value, and the follow-up delete prevents duplicate values from remaining in the tree.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(h), where h is the tree height, because you follow one search path to the target and, in the two-child case, one additional path to find and remove the inorder successor. In a balanced BST this is O(log n), but in a skewed tree it degrades to O(n). Space is O(h) for the recursive call stack, or O(1) extra if you implement the same pointer updates iteratively.

What Interviewers Usually Probe

They want to see whether you separate the search phase from the subtree-rewiring phase instead of mixing cases too early.
They are checking whether you know why the inorder successor or predecessor preserves BST order for the two-child delete case.
They care about whether your function returns the new subtree root correctly, especially when deleting the original root node.

Common Pitfalls or Variants

Common pitfalls

Replacing a two-child node's value with its successor but forgetting to delete the successor node, which leaves a duplicate in the BST.
Updating the child pointer locally but not returning it upward, causing the parent link or root replacement to stay stale.
Using a generic binary-tree delete idea that ignores BST ordering and accidentally breaks the in-order sorted property.

Follow-up variants

Use the inorder predecessor from the left subtree instead of the successor from the right subtree for the two-child case.
Write the deletion iteratively by tracking the parent pointer, which removes recursion but makes edge handling around the root more manual.
Augment the BST with parent pointers or subtree metadata, where deletion still follows the same cases but requires extra state updates after relinking.

FAQ

What is the core idea behind Delete Node in a BST?

The core idea is to use BST search to locate the target, then reconnect the subtree based on how many children that node has. Zero children means remove it, one child means promote that child, and two children usually means copy in the inorder successor and then delete that successor from the right subtree.

Why does replacing with the inorder successor work in Delete Node in a BST?

The inorder successor is the smallest value in the target node's right subtree, so it is larger than everything on the left and no larger than the remaining values on the right. That makes it a safe replacement that preserves BST ordering after the original node's value is overwritten.

Can I use the inorder predecessor instead of the successor?

Yes. The predecessor, which is the largest value in the left subtree, is equally valid. The choice usually comes down to implementation preference, but you must consistently remove the moved value from the subtree it came from.

What pattern is this problem testing?

This problem tests binary-tree traversal and state tracking under BST constraints. You are not just visiting nodes; you are returning updated subtree roots after structural changes, which is the state-management detail that interviewers usually focus on.

What happens if the key is not present in the tree?

You simply return the original BST unchanged. A clean solution keeps descending left or right until it hits null, then bubbles the unchanged subtree roots back up without modifying any links.

terminal

Solution

Solution 1

#### Python3

# 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

Continue Practicing

#449 serialize and deserialize bst #501 find mode in binary search tree #530 minimum absolute difference in bst