Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestKValues(self, root, target, k):
        def inorder(node):
            if not node:
                return []
            return inorder(node.left) + [node.val] + inorder(node.right)
        vals = inorder(root)
        vals.sort(key=lambda x: abs(x - target))
        return vals[:k]
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
class Solution {
public:
    vector closestKValues(TreeNode* root, double target, int k) {
        vector vals;
        inorder(root, vals);
        sort(vals.begin(), vals.end(), [target](int a, int b) {
            return abs(a - target) < abs(b - target);
        });
        return vector(vals.begin(), vals.begin() + k);
    }
private:
    void inorder(TreeNode* node, vector& vals) {
        if (!node) return;
        inorder(node->left, vals);
        vals.push_back(node->val);
        inorder(node->right, vals);
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
class Solution {
    public List closestKValues(TreeNode root, double target, int k) {
        List vals = new ArrayList<>();
        inorder(root, vals);
        vals.sort((a, b) -> Double.compare(Math.abs(a - target), Math.abs(b - target)));
        return vals.subList(0, k);
    }
    private void inorder(TreeNode node, List vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
var closestKValues = function(root, target, k) {
    const vals = [];
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        vals.push(node.val);
        inorder(node.right);
    }
    inorder(root);
    vals.sort((a, b) => Math.abs(a - target) - Math.abs(b - target));
    return vals.slice(0, k);
};
      

Problem Description

Given the root of a binary search tree (BST), a target value, and an integer k, find the k values in the BST that are closest to the target. The result can be returned in any order. Each value in the BST is unique, and you should not reuse elements. There is always at least one valid solution.

• Input: root (the root node of the BST), target (a floating-point number), k (an integer)
• Output: A list of k integers from the BST closest to target
• Constraints: BST property holds, all node values are unique, 1 ≤ k ≤ total nodes

Thought Process

To solve this problem, we need to identify which k node values in the BST are numerically closest to the given target value. The most straightforward (brute-force) approach would be to traverse the entire tree, collect all values, compute their distance to the target, sort them by this distance, and pick the closest k.

However, since the input is a BST, we can consider optimizations. For example, an in-order traversal yields values in sorted order, which can help us efficiently find the closest values using two pointers or a sliding window. This leverages the BST's structure to avoid unnecessary computation.

The main challenge is balancing efficiency (not traversing more nodes than needed) with correctness (always finding the closest k values, even if they're distributed across the tree).

Solution Approach

• Step 1: In-order Traversal
  • Perform an in-order traversal of the BST to collect all node values in a sorted list.
• Step 2: Sort by Closeness
  • Sort the collected values based on their absolute difference from the target.
• Step 3: Select Closest k Values
  • Pick the first k values from the sorted list, as these are the closest to the target.

Why this approach?

• In-order traversal ensures we visit every node and get all values.
• Sorting by distance guarantees we can easily pick the closest values.
• While there are more optimal methods (like using two stacks to track predecessors and successors), this approach is simple, easy to implement, and sufficient for most constraints.

Example Walkthrough

Sample Input:

• BST: [4, 2, 5, 1, 3]
• target = 3.714286
• k = 2

1. Perform in-order traversal: [1, 2, 3, 4, 5]
2. Compute distances to target:
   • |1 - 3.714| ≈ 2.714
   • |2 - 3.714| ≈ 1.714
   • |3 - 3.714| ≈ 0.714
   • |4 - 3.714| ≈ 0.286
   • |5 - 3.714| ≈ 1.286
3. Sort by distance: [4 (0.286), 3 (0.714), 5 (1.286), 2 (1.714), 1 (2.714)]
4. Pick first k=2 values: [4, 3]

Result: [4, 3] (order does not matter)

Time and Space Complexity

• Brute-force approach:
  • Time: O(N log N) (due to sorting N elements)
  • Space: O(N) (to store all node values)
• Optimized approach (not shown in code above):
  • Time: O(k + log N) (using two stacks for predecessors/successors)
  • Space: O(k + log N)
• Why? In the shown solution, we must visit every node (O(N)), and sorting takes O(N log N). The space is for the list of values.

Summary

The strategy is to traverse the BST, collect all values, and select the k closest values to the target. This method is straightforward, leverages the BST's properties for traversal, and guarantees correctness. While more advanced approaches exist, this solution is easy to implement and understand, making it a solid choice for most use cases.