Nearest Shelf Label
EasyTrees
Problem
A library stores its shelf labels (distinct integers) in a non-empty binary search tree. A visitor asks for a target number that may not exist as a label.
Return the label whose absolute difference to target is smallest. If two labels are equally close, return the smaller one.
Example 1
- Input:
- root = [10, 5, 15, 2, 7, null, 20], target = 12
- Output:
- 10
|12 - 10| = 2 beats |15 - 12| = 3.
Example 2
- Input:
- root = [10, 5, 15, 2, 7, null, 20], target = 6
- Output:
- 5
5 and 7 are both 1 away; the tie goes to the smaller label.
Example 3
- Input:
- root = [1], target = 100
- Output:
- 1
Constraints
- 1 ≤ number of nodes ≤ 10^4
- -10^8 ≤ node.val, target ≤ 10^8
- All labels are distinct and form a valid search tree.
Hint
Show the first hint
The closest label lies on the path you would follow if you were searching for target.
Walkthrough
How to approach it
01Clarify before coding
- How are ties broken? The smaller label wins.
- Can the tree be empty? No, at least one node exists, so there is always an answer.
- Is target guaranteed to be in the tree? No; it may be outside the whole range.
02Brute force
Visit every node and keep the one with the smallest distance (ties to the smaller value).
Cost: O(n) time: correct, but it never uses the ordering of the tree.
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.