← DSA Atlas
Dedicated problem page · #450

Delete Node in a BST

MediumTrees and Binary Search TreesBST delete with successor replacementRecursive binary search tree surgery
Solve on LeetCode ↗
450
MediumTrees and Binary Search TreesRecursive binary search tree surgeryBST delete with successor replacement

Delete Node in a BST

Given the root of a binary search tree and a key, delete the node with that key (if it exists) and return the root of the modified BST. The result must remain a valid BST.

Open official problem prompt ↗
In plain English

Remove one keyed node from a BST while keeping every remaining node in sorted order.

Picture it like this

Removing a manager from an org chart: if they have one report, that report moves up; if they have two teams, promote the most-junior person from the right team into the vacant seat.

Example
Input
root = [5,3,6,2,4,null,7], key = 3
Output
[5,4,6,2,null,null,7]
Why
Node 3 has two children, so it is replaced by its in-order successor 4, and the duplicate 4 is removed from the right subtree.
Constraints
The number of nodes is in the range [0, 10^4]-10^5 <= Node.val <= 10^5Each node has a unique valueroot is a valid binary search tree-10^5 <= key <= 10^5
Pattern lesson

See the pattern, then code

BST delete with successor replacement
Recognition clue

A modification to a BST that must preserve the BST ordering property, keyed by value, is the classic three-case delete: leaf, one child, or two children.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Use the BST ordering to descend to the target in O(h). Once found, a node with fewer than two children is spliced out directly; a node with two children is overwritten by its in-order successor (smallest value in the right subtree), then that successor is deleted from the right subtree.

New words, made simpleKnow these before the algorithm
In-order successor
The next-larger value, found as the leftmost node of the right subtree.
Splice out
Bypass a node by returning its single child to the parent.
BST property
Every left descendant is smaller and every right descendant is larger than a node.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Rebuild by re-inserting

Discards the existing structure and touches every node; wasteful and can unbalance the tree.

Collect all values except the key, then build a fresh BST by inserting them.

Time O(n)Space O(n)
Best choiceRecursive three-case delete

Only the search path is touched and the BST property is preserved locally; optimal.

Search to the node in O(h), then handle leaf/one-child/two-children locally using the successor.

Time O(h)Space O(h)
The rule we keep true

Invariant

Each recursive call returns a valid BST rooted at the node it was given, with the key removed from that subtree; the parent re-attaches the returned subtree.

Why this is correct

Reasoning

Descending by comparison locates the unique node in O(h). For zero or one child, returning the child keeps ordering because the child subtree already satisfies the BST property relative to the ancestors. For two children, the in-order successor is the smallest value greater than the node, so placing it in the node's slot keeps everything to the left smaller and everything else to the right larger; deleting that successor (which has no left child) is a simpler one-child case.

The algorithm in three movesSay these aloud before coding
1Recurse left if key < node.val, right if key > node.val

descend: 3 < 5 -> go left

2When found with no left child, return the right child (and vice versa)

found 3, two children

3For two children, find the leftmost node of the right subtree (successor)

successor = 4; copy into node; delete 4 on right

4Copy the successor's value into the node, then delete the successor from the right subtree

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
50
31
62
23
44
75
1 · Readkey 3
2 · Ask3 < 5?
3 · Update staterecurse into left child 3
4 · Resultroot.left = delete(3-subtree)
Key takeaway

Node 3 (two children) is replaced by successor 4, then 4 is removed from its right subtree.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-8Search by comparison

    Recurse into the side that could contain the key and reassign that child to the returned subtree.

  2. 2
    Lines 10-13Zero/one-child cases

    Return the non-null child (or None), which the parent splices in.

  3. 3
    Lines 14-18Two-child case

    Find the in-order successor, copy its value up, then delete it recursively from the right subtree.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Key not present: tree returned unchanged
  • Deleting the root itself
  • Deleting a leaf
  • Node with only a left or only a right child
  • Empty tree
!

Common beginner mistakes

  • Returning the wrong child in the one-child case
  • Searching the left subtree for the successor instead of the leftmost of the right subtree
  • Forgetting to re-delete the successor after copying its value, leaving a duplicate
  • Not reassigning root.left/root.right to the recursive result
Check your understanding

Why is the in-order successor guaranteed to have no left child?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split