AlgoViz
HomeBinary Search Trees

Delete a node in BST

Medium

Three cases; two children is the interesting one

Problem

Delete a node with a given key from a BST and return the root, keeping it a valid BST.

In simple words

Find the node; if it has two children, swap in its smallest right-subtree value, then delete that.

The idea

A leaf is simply removed and a node with one child is replaced by that child. With two children, swap in the in-order successor — the smallest value on the right — because it is the only value that keeps everything on both sides correctly ordered, then delete that successor from the right subtree.

The trick

  • In-order successor = leftmost node of the right subtree.
  • The predecessor (rightmost on the left) works equally well.
  • The successor has at most one child, so its own deletion is an easy case.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
3
6
2
4
7
3
0
1
2
3
4
5
6

Step 1 of 2. Here's the example — root=[5,3,6,2,4,null,7], key=3 Values: 5, 3, 6, 2, 4, 7, 3.

1/2
Optimal
timeO(h)spaceO(h)
1find node; if it has two children:2  succ = leftmost of right subtree3  node.val = succ.val; delete succ from right subtree4else splice past it

Input

array
[5, 3, 6, 2, 4, 7, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
bst = [5,3,6,2,4,null,7], delete = 3
Output:
[[5], [4, 6], [2, 7]]
Explanation:
3 is replaced by its in-order successor.

Example 2

Input:
bst = [5,3,6], delete = 6
Output:
[[5], [3]]
Explanation:
Deleting a leaf just removes it.

Example 3

Input:
bst = [2,1], delete = 2
Output:
[[1]]
Explanation:
Removing the root promotes its child.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.