Closest K values in a BSt

XXX. Closest K Values in a BST

Tree

In-Order Traversal

Problem Statement:

Given the root of a binary search tree (BST), a target value, and an integer k, return the k values in the BST that are closest to the target. The result can be returned in any order.

Algorithm:

1. Perform an in-order traversal of the BST to process nodes in sorted order.
2. Maintain a sliding window of size k using a deque (linked list):
• If the deque size is less than k, add the current node's value.
• Otherwise, compare the absolute difference between the target and the current value with the target and the first value in the deque:
• If the current value is closer, replace the first value in the deque with the current value.
• Otherwise, terminate traversal early, as all subsequent values will be further away.
3. Return the deque as the result.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the BST (for in-order traversal).
Space Complexity: O(k) for storing the closest values.

Java Implementation:

public List closestKValues(TreeNode root, double target, int k) {
    LinkedList result = new LinkedList<>(); // Store the closest k values
    Stack stack = new Stack<>(); // Stack for in-order traversal
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // Traverse to the leftmost node
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop(); // Process the current node

        if (result.size() < k) {
            result.add(current.val); // Add the value if the result size is less than k
        } else {
            double diff = Math.abs(target - current.val); // Difference with the target
            double firstDiff = Math.abs(target - result.getFirst()); // Difference with the first value in the deque

            if (diff < firstDiff) {
                result.pollFirst(); // Remove the farthest value
                result.add(current.val); // Add the closer value
            } else {
                break; // Terminate early if the current value is farther
            }
        }

        current = current.right; // Move to the right subtree
    }

    return result;
}
                

Python Implementation:

def closest_k_values(root, target, k):
    result = deque() # Store the closest k values
    stack = [] # Stack for in-order traversal
    current = root

    while current or stack:
        # Traverse to the leftmost node
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop() # Process the current node

        if len(result) < k:
            result.append(current.val) # Add the value if the result size is less than k
        else:
            diff = abs(target - current.val) # Difference with the target
            first_diff = abs(target - result[0]) # Difference with the first value in the deque

            if diff < first_diff:
                result.popleft() # Remove the farthest value
                result.append(current.val) # Add the closer value
            else:
                break # Terminate early if the current value is farther

        current = current.right # Move to the right subtree

    return list(result)
                

C++ Implementation:

#include 
#include 
#include 
#include 
using namespace std;

vector closestKValues(TreeNode* root, double target, int k) {
    deque result; // Store the closest k values
    stack stack; // Stack for in-order traversal
    TreeNode* current = root;

    while (current || !stack.empty()) {
        // Traverse to the leftmost node
        while (current) {
            stack.push(current);
            current = current->left;
        }

        current = stack.top();
        stack.pop(); // Process the current node

        if (result.size() < k) {
            result.push_back(current->val); // Add the value if the result size is less than k
        } else {
            double diff = abs(target - current->val); // Difference with the target
            double firstDiff = abs(target - result.front()); // Difference with the first value in the deque

            if (diff < firstDiff) {
                result.pop_front(); // Remove the farthest value
                result.push_back(current->val); // Add the closer value
            } else {
                break; // Terminate early if the current value is farther
            }
        }

        current = current->right; // Move to the right subtree
    }

    return vector(result.begin(), result.end());
}