Frontend School

K Closest Values in a Binary Search Tree

DSA
medium

K Closest Values in a Binary Search Tree

Medium
Tree
BST
Depth-First Search
Two Pointers
Stack

Overview

Meesho's product catalog is vast, and efficiently recommending items similar to a user's preference is crucial for engagement. Imagine a scenario where product attributes (e.g., price, rating, or a synthetic similarity score) are organized into a Binary Search Tree (BST) for optimized lookup. When a user expresses interest in a particular value (e.g., a specific price point), we need to quickly find k products whose attribute values are closest to this target.

What you need to do / Task

Implement a function kClosestValues that, given the root of a Binary Search Tree (BST), a target floating-point value, and an integer k, returns a list of k values from the BST that are closest to the target.

  • The returned list should be sorted in ascending order.
  • If there's a tie in absolute difference to the target, the smaller value from the BST should be preferred.
  • Assume k is always valid (i.e., 1 <= k <= total number of nodes).

Input & output

Input:

  • root: The root node of a Binary Search Tree. Each node has val (a number), left (TreeNode), and right (TreeNode).
  • target: A number representing the target value.
  • k: An number representing the count of closest values to find.

Output:

  • An array of numbers, representing the k closest values from the BST to the target, sorted in ascending order.

Clarifications

  • The BST contains unique integer values.
  • The target can be a floating-point number and might not exist in the BST.
  • The BST nodes' values are integers.

Examples

1

Example 1

Input:

root = [4,2,5,1,3], target = 3.7, k = 2

Output:

[3,4]

Note:

The values in the BST are [1, 2, 3, 4, 5]. Differences: | Value | Diff to 3.7 | | :---- | :---------- | | 1 | 2.7 | | 2 | 1.7 | | 3 | 0.7 | | 4 | 0.3 | | 5 | 1.3 | The 2 closest values are 4 (diff 0.3) and 3 (diff 0.7). Sorted, they are [3, 4].

2

Example 2

Input:

root = [1], target = 0.5, k = 1

Output:

[1]

Note:

The only value in the BST is 1. Its difference to 0.5 is 0.5.

3

Example 3

Input:

root = [2,1,3], target = 2.0, k = 3

Output:

[1,2,3]

Note:

All nodes are equally close in terms of relative ordering. Since k=3, all nodes are returned in ascending order.

Constraints

Constraints & assumptions

  • Number of nodes in the BST: 1 <= N <= 10^4
  • Node values: -10^9 <= Node.val <= 10^9
  • Target value: -10^9 <= target <= 10^9
  • 1 <= k <= N
  • The BST is guaranteed to be valid.

What interviewers evaluate

  • Correctness: Does the solution correctly identify the k closest values, handling ties and ordering?
  • Efficiency: Is the algorithm time and space efficient, leveraging BST properties?
  • Edge Cases: Does the solution handle small BSTs, k=1, and target values outside the BST range?
  • Code Quality: Is the code clean, readable, and well-structured?

Loading editor...