Quick Overview

Given a binary search tree described by its preorder traversal, a real-valued target and an integer k, return the k node values closest to the target in ascending order, breaking distance ties toward the smaller value. Tests binary search tree traversal, reasoning over ordered data and precise tie handling.

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

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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 ```python 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** ```text 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** ```text 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** ```text 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.

Overview: Given a binary search tree described by its preorder traversal, a real-valued target and an integer k, return the k node values closest to the target in ascending order, breaking distance ties toward the smaller value. Tests binary search tree traversal, reasoning over ordered data and precise tie handling.

Read the full LinkedIn Software Engineer interview experience this question came from

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. The tree is given as `preorder`, the list of its node values 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. Given `preorder`, a real number `target` and an integer `k`, return the `k` values in the tree that are closest to `target`. **Rules** - The distance of a value `v` from the target is `|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. **Example 1** ```text 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** ```text 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. **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 Every tree value fits in a 32-bit signed integer, but the distance between a value and `target` can reach `2 * 10^9`, which exceeds `2^31 - 1`; compute distances in floating-point (or 64-bit) arithmetic.

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

Input: ([4, 2, 1, 3, 5], 3.7, 2)

Expected Output: [3, 4]

Explanation: Source Example 1: 4 (0.3) and 3 (0.7) are the two closest; the answer is ascending [3, 4], not closeness order [4, 3].

Input: ([8, 3, 1, 6, 4, 7, 10, 14, 13], 5.5, 2)

Expected Output: [4, 6]

Explanation: Source Example 2: 6 is 0.5 away; 4 and 7 tie at 1.5 (half-integer midpoint) and the smaller value 4 takes the second slot.

Hints

  1. Every value's closeness is measured only by |v - target|; when two values are exactly as far away, the larger one loses.
  2. Equal distances can only happen when target lies exactly midway between two values, and such a tie can decide which value fills the k-th slot.
  3. The answer must be listed in ascending order of value, not in order of closeness.

Loading coding console...

Show the approach

Approach

Algorithm: the preorder list contains exactly the tree's values, and an in-order walk of a binary search tree visits them in ascending order, so sorting the list reproduces that in-order sequence. Rank values by the key (distance, value); because the smaller value wins an equal distance, this is a strict total order and the answer is the k smallest values under it. That set is a contiguous window of the sorted array around the target: if a value v is chosen, every value strictly between v and the target on the same side is strictly closer and must be chosen too. Binary search finds the first index whose value is >= target; left starts just before it and right at it. Repeat k times: if the low side is exhausted take values[right], if the high side is exhausted take values[left], otherwise take values[left] when target - values[left] <= values[right] - target (on an equal distance the left value is the smaller one, so it wins) and values[right] otherwise. Invariant: after i steps values[left+1 .. right-1] are exactly the i closest values, because the closest value not yet taken is always one of the two frontier values. The final window is already in ascending order. Edge cases: a single node; target below the minimum or above the maximum (one frontier is empty from the start); k = len(preorder) (the window grows to the whole array); target equal to a tree value (distance 0, taken first); exact midpoint ties, which arise only when target is an integer or half-integer and are therefore exact in double arithmetic; any non-tie gap between two distances is at least 0.02, far above double rounding error at magnitude 2 * 10^9, and distances up to 2 * 10^9 never pass through 32-bit integer arithmetic.

Time complexity:
O(n log n)
Space complexity:
O(n)