K Closest Values in a Binary Search Tree
Meesho's product catalog is vast, and efficiently recommending items similar to a user's preference is crucial for engagement. Imagine a scenario where product attributes (e.g., price, rating, or a synthetic similarity score) are organized into a Binary Search Tree (BST) for optimized lookup. When a user expresses interest in a particular value (e.g., a specific price point), we need to quickly find k products whose attribute values are closest to this target.
Implement a function kClosestValues that, given the root of a Binary Search Tree (BST), a target floating-point value, and an integer k, returns a list of k values from the BST that are closest to the target.
k is always valid (i.e., 1 <= k <= total number of nodes).Input:
root: The root node of a Binary Search Tree. Each node has val (a number), left (TreeNode), and right (TreeNode).target: A number representing the target value.k: An number representing the count of closest values to find.Output:
numbers, representing the k closest values from the BST to the target, sorted in ascending order.target can be a floating-point number and might not exist in the BST.Examples
Example 1
Input:
root = [4,2,5,1,3], target = 3.7, k = 2
Output:
[3,4]
Note:
The values in the BST are [1, 2, 3, 4, 5]. Differences: | Value | Diff to 3.7 | | :---- | :---------- | | 1 | 2.7 | | 2 | 1.7 | | 3 | 0.7 | | 4 | 0.3 | | 5 | 1.3 | The 2 closest values are 4 (diff 0.3) and 3 (diff 0.7). Sorted, they are [3, 4].
Example 2
Input:
root = [1], target = 0.5, k = 1
Output:
[1]
Note:
The only value in the BST is 1. Its difference to 0.5 is 0.5.
Example 3
Input:
root = [2,1,3], target = 2.0, k = 3
Output:
[1,2,3]
Note:
All nodes are equally close in terms of relative ordering. Since k=3, all nodes are returned in ascending order.
Constraints
1 <= N <= 10^4-10^9 <= Node.val <= 10^9-10^9 <= target <= 10^91 <= k <= Nk closest values, handling ties and ordering?k=1, and target values outside the BST range?Loading editor...