All problems

Nearest Park Benches

Medium · tree dfs

A long path through a park has benches at various distances (in metres) from the gate. The distances of all the benches are stored in a binary search tree with the given root.

A group of friends stands at distance target from the gate and wants to sit on the k benches that are closest to them, where closeness means the absolute difference |bench - target|. If two benches are equally close, the one with the smaller distance from the gate counts as closer.

Return the distances of those k benches as a list in increasing order. There are always at least k benches.

In a binary search tree, for every node all values in its left subtree are smaller and all values in its right subtree are larger. All distances are distinct.

Examples

Example 1

Input: root = [40, 20, 60, 10, 30, 50, 70], target = 34, k = 3

Output: [20, 30, 40]

The distances from 34 are 4 for the bench at 30, 6 for 40, 14 for 20 and 16 for 50. The three closest are 30, 40 and 20, listed in increasing order.

Example 2

Input: root = [10, 5, 15], target = 10, k = 2

Output: [5, 10]

The bench at 10 is closest. The benches at 5 and 15 are both 5 away, so the smaller one, 5, is taken.

Constraints

• 1 <= number of nodes <= 2000
• 0 <= Node.val <= 10^6, and all values are distinct.
• The tree is a valid binary search tree.
• 0 <= target <= 10^6
• 1 <= k <= number of nodes