K Closest Values in a Binary Search Tree
Updated
Problem statement
Given the root of a binary search tree with distinct integer keys, a real-valued target and an integer k, return the k node values closest to the target.
For this exercise, assume values are ranked by increasing absolute distance from the target; for equal distances the smaller value ranks first. Return the selected values in that ranked order, not tree traversal order. Do not change the tree.
Function
closestValues(root: TreeNode, target: double, k: int) → int[]Examples
Example 1
root = [6,3,9,1,4,8,12]target = 5.5k = 4return = [6,4,3,8]The four closest values, in ranked order, are 6, 4, 3 and 8, at distances 0.5, 1.5, 2.5 and 2.5. The last pair ties, so the smaller value 3 comes before 8.
Example 2
root = [5,2,8]target = 3.5k = 2return = [2,5]Values 2 and 5 are both 1.5 from 3.5. The smaller value 2 comes first; value 8 is farther away.
Example 3
root = [7]target = 10.0k = 1return = [7]The tree has one node, so selecting one value returns [7].
Constraints
- For this exercise, assume
rootis a nonempty strict binary search tree with distinct integer keys. - For this exercise, assume the tree has
1through10000nodes and its level-order serialization has at most19999entries, includingnullmissing-child markers. - For this exercise, assume
-1000000 <= node.val <= 1000000. - For this exercise, assume
-1000000 <= target <= 1000000, with a finite target. - For this exercise, assume
1 <= k <= number of nodes.