Shelve a New Key
MediumTrees
Problem
Insert key into a binary search tree of distinct values. key is guaranteed not to be in the tree yet.
Place it as a new leaf exactly where an unsuccessful search for key falls off the tree (do not rebalance or restructure anything else), and return the root. Inserting into an empty tree returns a single node.
Example 1
- Input:
- root = [4, 2, 7, 1, 3], key = 5
- Output:
- [4, 2, 7, 1, 3, 5]
5 > 4 → go to 7; 5 < 7 and 7 has no left child, so 5 becomes 7's left child.
Example 2
- Input:
- root = [40, 20, 60, 10, 30, 50, 70], key = 25
- Output:
- [40, 20, 60, 10, 30, 50, 70, null, null, 25]
Example 3
- Input:
- root = [], key = 5
- Output:
- [5]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^8 ≤ node.val, key ≤ 10^8
- key does not appear in the tree.
Hint
Show the first hint
Where would a search for key end if key is not in the tree?
Walkthrough
How to approach it
01Clarify before coding
- Can the key already exist? No, it is guaranteed new.
- Should the tree be rebalanced? No: insert as a leaf at the search position so the result is unique.
- Empty tree? The new node becomes the root.
02Brute force
Dump the values in order, add key, and rebuild a tree from the sorted list.
Cost: O(n) time and space, and it changes the shape, which the problem forbids.
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.