Delete Node in a BST

Given the root of a binary search tree and a key, delete the node with that value (if present) and return the root of the updated BST, keeping it a valid BST.

The tree is given/returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Deletion is search plus three cases at the found node.

Zero or one child: splice the node out by returning its (only) child.

Two children: replace the value with the inorder successor (min of the right subtree), then delete that successor.

Common doubts

It's the smallest value larger than the node, so it can sit in the node's place without breaking the ordering — and you could symmetrically use the predecessor (max of the left subtree).

The successor is the leftmost node of the right subtree, so it has no left child — a 0/1-child splice.

The search falls off the tree and you return it unchanged.

Interview follow-ups

· What an interviewer asks next.

Yes — the largest value in the left subtree also preserves the invariant; the resulting tree just differs slightly.

Same three cases, then rotations/recoloring on the way up to restore balance (AVL/red-black).

Fun facts

Repeated deletions using only the successor can gradually skew a tree left — some implementations alternate successor/predecessor to keep it balanced.
The two-child case is the only tree operation where you copy a value rather than move a pointer.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [5, 3, 6, 2, 4, null, 7], key = 3
Output: [5, 4, 6, 2, null, null, 7]
3 has two children; it's replaced by its inorder successor 4.

Example 2

Input: root = [5, 3, 6, 2, 4, null, 7], key = 0
Output: [5, 3, 6, 2, 4, null, 7]
0 is not in the tree; nothing changes.

Constraints

- The number of nodes is in the range [0, 10^4] - -10^5 <= Node.val <= 10^5 - root is a valid BST - -10^5 <= key <= 10^5

Deletion is search plus three cases at the found node. If it has no child, drop it. If it has one child, splice that child into its place. If it has two children, you can't just remove it — replace its value with its inorder successor (the smallest value in the right subtree), then delete that successor (which has no left child, so it's an easy 0/1-child delete). O(height).

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left < node < right, everywhere.

Inorder successor. Smallest value in the right subtree — the next value in sorted order.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Cases

“Two-child node — what replaces it?”

Its inorder successor (min of the right subtree), then delete that successor.

“Key not in the tree?”

Return the tree unchanged.

The ideal opening — say it like this

I search for the key; at the node I split on how many children it has.

Zero or one child is a simple splice; two children I replace with the inorder successor and then delete that successor from the right subtree.

Understand the problem

Worked example — delete 3 from BST [5, 3, 6, 2, 4, null, 7]

        5                 5
       / \               / \
      3   6    delete 3  4   6      (successor of 3 is 4)
     / \   \    ----->  /     \
    2   4   7          2       7

Key observations

1Aha

Three cases at the node

Zero, one, or two children — only the two-child case needs a replacement.

2Aha

Successor keeps the order

The inorder successor is the smallest value larger than the node, so promoting it preserves the BST.

3Aha

The successor is easy to remove

It has no left child, so deleting it is a 0/1-child splice.

Brute force vs optimal

	Recursive delete	Iterative (find + splice)
Idea	Recurse to the node; handle 3 cases	Find node + parent, splice out
Time	O(height)	O(height)
Space	O(height)	O(1)

Both promote the same inorder successor, so they yield the same tree. Full code is in the Approaches selector below.

Summary

Key takeaway

Find the node; 0/1 child is a splice, 2 children replaces the value with the inorder successor then deletes the successor. O(height).

if key < node: recurse left
elif key > node: recurse right
else:
    if a child is missing: return the other child
    else: node.val = min(right subtree); delete that value from the right subtree