Skip to content
MediumTreesAI interview only

Delete Node In BST

Asked atamazonmicrosoftgooglemetaoraclebloomberg

01 · Problem

You are given the root of a binary search tree (BST) with distinct values and an integer key. Remove the node whose value is key (if such a node exists) and return the root of the resulting BST.

Because several valid BSTs can result from a deletion, follow this exact rule so the output is unique:

  • If the node is a leaf, simply remove it.
  • If the node has exactly one child, replace the node with that child.
  • If the node has two children, copy the value of its inorder successor (the smallest value in its right subtree) into the node, then delete that successor from the right subtree using the same rules.

If key is not present, return the tree unchanged. Trees are given and returned in level-order form, with null marking missing children (trailing nulls omitted).

02 · Examples

Example 01
Input
root = [5,3,6,2,4,null,7], key = 3
Output
[5,4,6,2,null,null,7]

Node 3 has two children. Its inorder successor is 4, so 3 is overwritten with 4 and the original leaf 4 is removed.

Example 02
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, so nothing changes.

Example 03
Input
root = [], key = 0
Output
[]

Deleting from an empty tree yields an empty tree.

03 · Constraints

  • 01The number of nodes in the tree is in the range [0, 104].
  • 02-105 <= Node.val <= 105
  • 03All node values are unique.
  • 04The input tree is a valid binary search tree.
  • 05-105 <= key <= 105

04 · Optimal complexity

Time
O(h)
Space
O(h)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem