Closest Binary Search Tree Value II

HardTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the root of a binary search tree with distinct values, a real number target, and an integer k. Return the k values in the tree that are closest to target, measured by absolute difference. When two values are equally close, the **smaller** value is preferred. Return the chosen k values sorted in **ascending** order. A full traversal plus sorting is O(n log n). Try for O(n) by scanning the in-order sequence, and as a follow-up, O(h + k) using two stacks of predecessors and successors.

Examples

Input: root = [8,3,10,1,6,null,14], target = 6.8, k = 3
Output: [6,8,10]
Distances are 6: 0.8, 8: 1.2, 10: 3.2, 3: 3.8. The three closest are 6, 8 and 10.
Input: root = [8,3,10,1,6,null,14], target = 9.0, k = 1
Output: [8]
8 and 10 are both 1 away; the smaller value is preferred.
Input: root = [1], target = 0.0, k = 1
Output: [1]
The only value is returned.

Constraints

  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^9
  • All node values are distinct
  • -10^9 <= target <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems