Find the Closest Binary Search Tree Value II

// TreeNode class to represent nodes in the BST
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Pair class for storing distance and value
class Pair {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }

    getKey() {
        return this.key;
    }

    getValue() {
        return this.value;
    }
}

// Function to find the k closest values in a binary search tree to a given target
function closestKValues(root, target, k) {
    // Max heap to store the k closest values and their distances from the target
    const maxHeap = new PriorityQueue((a, b) => b.key - a.key);

    // Recursive helper function to traverse the tree and find the closest values
    function solve(node) {
        if (!node) {
            return;
        }

        // Calculate the distance from the current node's value to the target
        const distanceFromTarget = Math.abs(node.val - target);

        // Push the node's value and distance onto the max heap
        maxHeap.push(new Pair(distanceFromTarget, node.val));

        // If the heap size exceeds k, remove the element with the largest distance
        if (maxHeap.size() > k) {
            maxHeap.pop();
        }

        // Recursively explore the left and right subtrees
        solve(node.left);
        solve(node.right);
    }

    // Traverse the tree and find the closest values
    solve(root);

    // Extract the k closest values from the max heap and store them in a list
    const result = [];
    while (!maxHeap.isEmpty()) {
        result.push(maxHeap.pop().value);
    }

    // Return the list of k closest values
    return result;
}

// Implementation of PriorityQueue in JavaScript
class PriorityQueue {
    constructor(comparator = (a, b) => a - b) {
        this.comparator = comparator;
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }

    pop() {
        if (this.isEmpty()) {
            return null;
        }
        this.swap(0, this.size() - 1);
        const removed = this.heap.pop();
        this.bubbleDown();
        return removed;
    }

    peek() {
        return this.isEmpty() ? null : this.heap[0];
    }

    bubbleUp() {
        let index = this.size() - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.comparator(this.heap[index], this.heap[parentIndex]) < 0) {
                this.swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    bubbleDown() {
        let index = 0;
        while (index < this.size()) {
            const leftChild = 2 * index + 1;
            const rightChild = 2 * index + 2;
            let smallerChild = leftChild;
            if (rightChild < this.size() && this.comparator(this.heap[rightChild], this.heap[leftChild]) < 0) {
                smallerChild = rightChild;
            }
            if (leftChild >= this.size() || this.comparator(this.heap[index], this.heap[smallerChild]) <= 0) {
                break;
            }
            this.swap(index, smallerChild);
            index = smallerChild;
        }
    }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
}

// Example usage
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);

const target = 3.714286;
const k = 2;

const result = closestKValues(root, target, k);

console.log(`The closest ${k} values to ${target} are: ${result.join(' ')}`);