Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

[Problem Link]

Since this is a BST, if the current node is larger than target, we look in the left subtree, else in the right subtree. In the end we simply return the value we get back from our recursion or the current node value depending on whichever one is closer to target. Remember to account for null values when we encounter a leaf node.

Time complexity is O(lgN)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
var closestValue = function(root, target) {
    if (!root) return null;
 
    let minNext;
    if (root.val > target) minNext = closestValue(root.left, target);
    else minNext = closestValue(root.right, target); 
 
    let minCurrDist = Math.abs(root.val-target);
    let minNextDist = minNext !== null ? Math.abs(minNext-target) : Number.MAX_VALUE;
 
    return minNextDist < minCurrDist ? minNext: root.val;
};

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

[Problem Link]

Traverse the full tree and keep storing closest distances (to target) in a priority queue. In the end, pop k number of elements from the queue and return the result. Note, the priority queue will be ordered based on distance (and not on the node values).

Time complexity will be O(NLgN), insert N items into a heap.
If we decide to keep the heap size k, it goes to O(NLgK).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
class Node implements Comparable<Node> {
    int val;
    double dist;
    public Node(int val, double dist) {
        this.val = val;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist < o.dist ? -1 : 1;
    }
}
 
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        traverseBST(root, target, q);
        List<Integer> ret = new ArrayList<Integer>();
        for ( int i = 0 ; i < k ; i++ ) {
            ret.add(q.poll().val);
        }
        return ret;
    }
 
    public void traverseBST(TreeNode root, double target, PriorityQueue<Node> q) {
        if ( root == null )
            return;
        q.offer(new Node(root.val, Math.abs(root.val - target)));        
        traverseBST(root.left, target, q);
        traverseBST(root.right, target, q);        
    }
}

Another approach would be to traverse (inOrder) through the tree to build a sorted array (i.e. O(n)). Then we use two pointers to get the subarray which has numbers closest to k (i.e. another O(n) time complexity).

Total time complexity for this is: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
 
function inOrder(root, arr) {
    if (!root) return;
 
    inOrder(root.left, arr);
    arr.push(root.val);
    inOrder(root.right, arr);
}
 
var closestKValues = function(root, target, k) {
    let ret = [];
    inOrder(root, ret);
    let i = 0;
    let j = ret.length - 1;
    while ((j-i+1) != k) {
        let iDist = Math.abs(ret[i] - target);
        let jDist = Math.abs(ret[j] - target);
        if ( iDist < jDist ) j--
        else i++
    }    
    let finalRet = [];
    for ( let start = i ; start <= j ; start++ ) finalRet.push(ret[start]);
    return finalRet;
};