Closest Binary Search Tree Value II

Problem

Find k values in the BST closest to target. Return them in any order.

Key insight: Get in-order (sorted) list and reverse in-order (reverse sorted). Use two-pointer approach to pick k closest values, like merging two sorted streams.

Solutions

// C++
vector<int> closestKValues(TreeNode* root, double target, int k) {
    vector<int> inorder;
    function<void(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return;
        dfs(node->left);
        inorder.push_back(node->val);
        dfs(node->right);
    };
    dfs(root);
    // two pointer on sorted array
    int lo = 0, hi = inorder.size() - 1;
    while (hi - lo + 1 > k) {
        if (abs(inorder[lo] - target) <= abs(inorder[hi] - target)) hi--;
        else lo++;
    }
    return vector<int>(inorder.begin() + lo, inorder.begin() + hi + 1);
}

// Java
public List<Integer> closestKValues(TreeNode root, double target, int k) {
    List<Integer> inorder = new ArrayList<>();
    inorderTraversal(root, inorder);
    int lo = 0, hi = inorder.size() - 1;
    while (hi - lo + 1 > k) {
        if (Math.abs(inorder.get(lo) - target) <= Math.abs(inorder.get(hi) - target)) hi--;
        else lo++;
    }
    return inorder.subList(lo, hi + 1);
}
void inorderTraversal(TreeNode node, List<Integer> list) {
    if (node == null) return;
    inorderTraversal(node.left, list);
    list.add(node.val);
    inorderTraversal(node.right, list);
}

// JavaScript
function closestKValues(root, target, k) {
    const inorder = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        inorder.push(node.val);
        dfs(node.right);
    }
    dfs(root);
    let lo = 0, hi = inorder.length - 1;
    while (hi - lo + 1 > k) {
        if (Math.abs(inorder[lo] - target) <= Math.abs(inorder[hi] - target)) hi--;
        else lo++;
    }
    return inorder.slice(lo, hi + 1);
}

# Python
def closestKValues(root, target, k):
    inorder = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        inorder.append(node.val)
        dfs(node.right)
    dfs(root)
    lo, hi = 0, len(inorder) - 1
    while hi - lo + 1 > k:
        if abs(inorder[lo] - target) <= abs(inorder[hi] - target):
            hi -= 1
        else:
            lo += 1
    return inorder[lo:hi + 1]

Complexity

Time: O(n)
Space: O(n)