Practice/LinkedIn/Leetcode 272. Closest Binary Search Tree Value II

Leetcode 272. Closest Binary Search Tree Value II

CodingMust

Problem

You are given the root of a binary search tree, a floating-point target value, and an integer k. Your task is to find the k values in the BST that are closest to the target value.

Return the k closest values as a list in any order. If two values have the same absolute difference from the target, either can be included in the result.

The key challenge is to leverage the BST property to find these k values efficiently, ideally without traversing the entire tree.

Requirements

1. Return exactly k values from the tree
2. The values should be the k closest to the target based on absolute difference
3. The output order does not matter
4. Handle edge cases like single-node trees and targets that match node values
5. Leverage BST properties for an efficient solution

Constraints

• The number of nodes in the tree is n where 1 ≤ n ≤ 10^4
• 1 ≤ k ≤ n
• 0 ≤ Node.val ≤ 10^9
• -10^9 ≤ target ≤ 10^9
• All node values are unique
• Target for optimal solution: O(log n + k) time complexity

Examples

Example 1:

Input: root = [4,2,5,1,3], target = 3.8, k = 3 Output: [4, 3, 5] Explanation: The distances are |4-3.8|=0.2, |3-3.8|=0.8, |5-3.8|=1.2 These are the three smallest distances.

Example 2:

Input: root = [1], target = 2.5, k = 1 Output: [1] Explanation: Only one node exists.

Example 3:

Input: root = [10,5,15,3,7,13,18], target = 7.0, k = 2 Output: [7, 5] Explanation: 7 has distance 0, and 5 has distance 2. These are the two closest.