Closest Binary Search Tree Value II

How it works

During inorder traversal, values are visited in sorted order. We can maintain a sliding window of size k using a deque. As we visit each node, we add it to the window. When the window exceeds k elements, we compare the distances of the first and last elements and remove the one farther from the target. Once the first element is closer, all subsequent elements will be even farther, so we can stop early.

Steps

1. Perform an inorder traversal of the tree.
2. Maintain a deque to store the current window of candidates.
3. For each visited node, append its value to the deque.
4. If the deque size exceeds k, compare the front and back elements. If the front is closer or equal, remove the back and stop traversing the right subtree. Otherwise, remove the front and continue.
5. Return the elements in the deque as the result.

Complexity

• Time complexity: O(n)
• Space complexity: O(n+k)

Where n is the number of nodes in the tree and k is the number of closest values to return

Things to watch for

Not Exploiting BST Property

Using a generic tree traversal and sorting all values works but misses the O(n + k) optimization possible with BST. Inorder traversal gives sorted values, enabling efficient sliding window approaches.

Off-by-One Errors in Binary Search

When using binary search to find the starting position for the sliding window, the insertion point may be at index 0 or n, causing out-of-bounds access when initializing the left pointer.

Using Wrong Heap Type

When using a heap to track k closest values, a max-heap is needed to evict the farthest element. Using a min-heap evicts the closest element instead, producing incorrect results.

Incorrect Tie-Breaking for Equal Distances

When two values have equal distance to target, the problem may require returning the smaller value. Failing to handle ties correctly can produce wrong results.

Stopping Early Without Checking Both Sides

In the sliding window approach, stopping as soon as one pointer goes out of bounds forgets to collect remaining elements from the other side.

from typing import List
from collections import deque

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(node, queue):
            if not node:
                return
            
            dfs(node.left, queue)
            queue.append(node.val)
            if len(queue) > k:
                if (abs(target - queue[0]) <= abs(target - queue[-1])):
                    queue.pop()
                    return
                else:
                    queue.popleft()
                    
            dfs(node.right, queue)
        
        queue = deque()
        dfs(root, queue)
        return list(queue)

class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        deque<int> queue;
        dfs(root, queue, k, target);
        return vector<int>(queue.begin(), queue.end());
    }
    
private:
    void dfs(TreeNode* node, deque<int>& queue, int k, double target) {
        if (node == nullptr) {
            return;
        }
        
        dfs(node->left, queue, k, target);
        
        queue.push_back(node->val);
        if (queue.size() > k) {
            if (abs(target - queue.front()) <= abs(target - queue.back())) {
                queue.pop_back();
                return;
            } else {
                queue.pop_front();
            }
        }
        
        dfs(node->right, queue, k, target);
    }
};