Remove a Catalog Entry
MediumTrees
Problem
A catalog of distinct integer IDs is kept in a binary search tree. Remove the node holding key (if there is one) and return the root of the updated tree.
Use exactly this rule so the result is unique: if the node has at most one child, replace it by that child (or by nothing). If it has two children, copy into it the value of its in-order successor (the smallest value in its right subtree), then remove that successor node, replacing it by its own right child. If key is absent, return the tree unchanged.
Example 1
- Input:
- root = [5, 3, 6, 2, 4, null, 7], key = 3
- Output:
- [5, 4, 6, 2, null, null, 7]
3 has two children; its successor is 4, which moves up into its place.
Example 2
- 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.
Example 3
- Input:
- root = [5, 3, 6, 2, 4, null, 7], key = 5
- Output:
- [6, 3, 7, 2, 4]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^5 ≤ node.val, key ≤ 10^5
- All values are distinct.
Hint
Show the first hint
Split into cases by how many children the doomed node has. Which cases are easy?
Walkthrough
How to approach it
01Clarify before coding
- What if the key is missing? Return the tree unchanged.
- Which replacement for a node with two children? The in-order successor, as specified, so the output is unique.
- Can I copy values between nodes? Yes, that is the stated rule.
02Brute force
Collect all values except key in order and rebuild a tree from them.
Cost: O(n) time and space, and it produces a different shape from the required one.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.