Delete Node in a BST

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary search tree with distinct values and an integer key. Remove the node whose value is key (if one exists) and return the root of the resulting BST. Many trees are valid results, so follow these exact rules: - If key is not in the tree, return the tree unchanged. - If the node has **no children**, simply remove it. - If it has **exactly one child**, that child's subtree takes the node's place. - If it has **two children**, overwrite the node's value with its **in-order successor** (the smallest value in its right subtree), then delete that successor node from the right subtree using these same rules (it never has a left child, so its right child takes its place). The tree is returned in level order. Aim for O(h) time where h is the tree height.

Examples

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 successor 4 takes its value and the original leaf 4 is removed.
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.
Input: root = [], key = 0
Output: []
Deleting from an empty tree yields an empty tree.

Constraints

  • 0 <= number of nodes <= 10^4
  • -10^5 <= Node.val, key <= 10^5
  • All values are distinct and the input is a valid BST

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems