Show problems as
Classic problem #450MediumTreeBinary Search TreeBinary Tree

Delete Node in a BST

Real-world version: Retire a Locker from the Sorted Index
Tracked in this browser only
Read Delete Node in a BST on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A depot keeps its locker codes in a binary search tree: every code in a node's left subtree is smaller than that node's code and every code in its right subtree is larger, and no code is stored twice.

The tree arrives as index, a level-by-level listing. index[0] is the root. After that, every node already listed contributes two entries in turn, its left child then its right child, with null where that child is missing. A null contributes nothing further, and null entries at the very end are left off. An empty listing means the tree is empty.

The locker with code code is being retired. Take its node out of the tree and return the resulting tree in the same level-by-level listing, again with trailing null entries left off. When no node holds code, hand back the tree as it arrived.

So that exactly one listing is correct, removal follows these rules:

  • a node with no children is dropped;
  • a node with a child on one side only is replaced by that child, whole subtree included;
  • a node with children on both sides stays where it is and takes on the smallest code held in its right subtree, and the node that held that smallest code is then taken out of the right subtree under these same rules.

What comes back is still a binary search tree.

Examples

Example 1

Input
index = [50, 30, 70, 20, 40, 60, 80], code = 50
Output
[60, 30, 70, 20, 40, null, 80]

The root holds 50 and has children on both sides. The smallest code in its right subtree is 60, so the root takes on 60, and the node that held 60 has no children of its own and is dropped from under 70.

Example 2

Input
index = [50, 30, 70, 20, 40, 60, 80], code = 20
Output
[50, 30, 70, null, 40, 60, 80]

The node holding 20 has no children, so it is dropped and every other node stays where it was.

Example 3

Input
index = [50, 30, 70, 20, 40, 60, 80], code = 99
Output
[50, 30, 70, 20, 40, 60, 80]

No node holds 99, so the listing comes back exactly as it arrived.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4].
  • -10^5 <= node code <= 10^5
  • Each node has a unique code.
  • index is a valid binary search tree.
  • -10^5 <= code <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def retire_locker(index: list[int | None], code: int) -> list[int | None]:
Java
public Integer[] retireLocker(Integer[] index, int code)

More on the same topics