507. Closest Keys Gap
A telescope catalogue stores star brightness readings in a binary search tree: keys in a node's left subtree are smaller, keys in its right subtree are larger, and no two stars share a reading. The astronomers want to know how close together the two most similar readings are.
Given root, return the smallest absolute difference between the keys of any two different nodes in the tree. The tree is guaranteed to have at least two nodes, so a pair always exists.
Example 1
- Input:
- root = [27,10,40,5,15,35,60]
- Output:
- 5
- Explanation:
In sorted order the keys are 5, 10, 15, 27, 35, 40, 60; the smallest gap between neighbouring keys is 5 (for example 5 and 10).
Example 2
- Input:
- root = [1,null,100]
- Output:
- 99
- Explanation:
Only two keys exist, 1 and 100, so the gap is 99.
Constraints
2 ≤ number of nodes ≤ 104
0 ≤ Node.val ≤ 109
The tree is a valid binary search tree with distinct keys.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)