K Keys Nearest to a Target

Hard

You are given the root of a binary search tree with distinct keys, a real number target and an integer k. Find the k keys in the tree that are nearest to target, that is, with the smallest |key - target|. The set of the k nearest keys is guaranteed to be unique. The keys may be returned in any order. Follow-up: if the tree is balanced, can you beat O(n) time?

Example 1

root=tree_node([20, 10, 30, 5, 15, None, 40]), target=17.5, k=3 → [10, 15, 20]

Distances from 17.5: 15 is 2.5 away, 20 is 2.5 away, 10 is 7.5 away, 30 is 12.5 away. The three nearest keys are 15, 20 and 10.

Example 2

root=tree_node([8, 3]), target=100.0, k=1 → [8]

The target is above every key, so the nearest one is the largest key, 8.

Constraints

Number of nodes n: 1 ≤ k ≤ n ≤ 10⁴
0 ≤ Node.val ≤ 10⁹, keys are distinct
-10⁹ ≤ target ≤ 10⁹
The set of the k nearest keys is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Tree Depth-First Search Binary Search Tree Two Pointers Binary Tree Heap (Priority Queue)

Similar problems

Pair Across Two Search Trees Medium Pair Sum in a Search Tree Easy Search Tree Into a Line Easy Heaviest Search Subtree Hard Left, Node, Right Easy

Input

root=tree_node([20, 10, 30, 5, 15, None, 40]), target=17.5, k=3

Expected

[10, 15, 20]

Run checks the first 3 tests in your browser. Submit checks all 53 tests on the server, hidden ones included.