Closest BST Values II

Given a BST, output the k closest values in this BST to x. Sort the output by value.

The output set is guaranteed to be unique.

Do not convert the BST to a list.

Input

• bst: a valid BST of size n.
• x: an integer representing the number to find the k closest numbers to.
• k: an integer.

Output

A list of integers containing the k closest numbers to x.

Examples

Example 1:

Input:

bst = <See explanation>
x = 7
k = 4

Output: [5, 6, 8, 10]

Explanation:

All four numbers in the output are within 3 away from 7.

Constraints

• 1 <= k <= n <= 10^5

Try it yourself

Solution