Find the K Values Closest to a Target in a Binary Search Tree

A binary search tree holds distinct integer values: for every node, every value in its left subtree is smaller than the node's value and every value in its right subtree is larger. Given the tree, a real number target and an integer k, return the k values in the tree that are closest to target.

Function Signature

def closest_k_values(preorder: list[int], target: float, k: int) -> list[int]:

The tree is passed as preorder, its node values listed in preorder: a node, then its left subtree, then its right subtree. Because the values are distinct and the tree is a binary search tree, this list determines the tree uniquely.

Rules

• The distance of a value v from the target is abs(v - target).
• When two values are equally far from the target, the smaller value counts as closer. Under this rule no two values are equally close, so exactly one set of k values is the closest.
• Return those k values in ascending order.

Constraints

• 1 <= len(preorder) <= 10^4
• -10^9 <= preorder[i] <= 10^9, and all values are distinct
• preorder is a valid preorder traversal of a binary search tree
• 1 <= k <= len(preorder)
• -10^9 <= target <= 10^9, with at most two digits after the decimal point

Examples

Example 1

Input: preorder = [4, 2, 1, 3, 5], target = 3.7, k = 2
Output: [3, 4]

The tree has root 4, whose left child 2 has children 1 and 3, and whose right child is 5. The distances are 0.3 for 4, 0.7 for 3, 1.3 for 5, 1.7 for 2 and 2.7 for 1, so the two closest values are 4 and 3, returned in ascending order.

Example 2

Input: preorder = [8, 3, 1, 6, 4, 7, 10, 14, 13], target = 5.5, k = 2
Output: [4, 6]

The tree has root 8. Its left subtree is rooted at 3, with children 1 and 6, and 6 has children 4 and 7. Its right subtree is rooted at 10, whose right child 14 has left child 13. The closest value is 6 (distance 0.5). Both 4 and 7 are 1.5 away, and the smaller value, 4, wins the tie.

Example 3

Input: preorder = [8, 3, 1, 6, 4, 7, 10, 14, 13], target = 12.25, k = 4
Output: [8, 10, 13, 14]

Same tree as Example 2. The distances are 0.75 for 13, 1.75 for 14, 2.25 for 10 and 4.25 for 8; the next closest value, 7, is 5.25 away.