Solutions

1. Sort With Custom Comparator

Intuition

The simplest approach is to collect all node values from the tree and then sort them based on their distance to the target. Once sorted, the first k elements are the closest values. This works because we just need the k values closest to the target, regardless of their original position in the tree.

Algorithm

Perform a DFS traversal to collect all node values into an array.
Sort the array using a custom comparator that compares the absolute difference between each value and the target.
Return the first k elements from the sorted array.

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(node, arr):
            if not node:
                return
            
            arr.append(node.val)
            dfs(node.left, arr)
            dfs(node.right, arr)
        
        arr = []
        dfs(root, arr)
        
        arr.sort(key = lambda x: (abs(x - target), x))
        return arr[:k]

Time & Space Complexity

Time complexity: $O(n \cdot \log n)$
Space complexity: $O(n)$

Where $n$ is the number of nodes in the tree

2. Traverse With Heap

Intuition

Instead of sorting all values, we can use a max-heap of size k to track the k closest values seen so far. As we traverse the tree, we compare each node's distance to the target with the farthest element in our heap. If the current node is closer, we replace the farthest element. This avoids sorting the entire array.

Algorithm

Create a max-heap that orders elements by their distance from the target (farthest at the top).
Traverse all nodes in the tree using DFS.
For each node, add its value to the heap. If the heap size exceeds k, remove the element with the largest distance.
Return all elements remaining in the heap.

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(node, heap):
            if not node:
                return

            if len(heap) < k:
                heappush(heap, (-abs(node.val - target), node.val))
            else:
                if abs(node.val - target) <= abs(heap[0][0]):
                    heappop(heap)
                    heappush(heap, (-abs(node.val - target), node.val))

            dfs(node.left, heap)
            dfs(node.right, heap)

        heap = []
        dfs(root, heap)
        return [x[1] for x in heap]

Time & Space Complexity

Time complexity: $O(n \cdot \log k)$
Space complexity: $O(n+k)$

Where $n$ is the number of nodes in the tree and $k$ is the size of our heap

3. Inorder Traversal + Sliding Window

Intuition

Since this is a BST, an inorder traversal gives us values in sorted order. With a sorted array, the k closest values to the target form a contiguous subarray. We can use binary search to find the position closest to the target, then expand outward using two pointers to collect the k nearest values.

Algorithm

Perform an inorder traversal to get all values in sorted order.
Use binary search to find the position where the target would be inserted.
Initialize two pointers: left pointing to the element just before the insertion point, right pointing at the insertion point.
Compare distances at both pointers and pick the closer one, moving that pointer outward. Repeat until k elements are collected.

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(node, arr):
            if not node:
                return
            
            dfs(node.left, arr)
            arr.append(node.val)
            dfs(node.right, arr)
        
        arr = []
        dfs(root, arr)
        
        left = bisect_left(arr, target) - 1
        right = left + 1
        ans = []
        
        while len(ans) < k:
            if right == len(arr) or abs(arr[left] - target) <= abs(arr[right] - target):
                ans.append(arr[left])
                left -= 1
            else:
                ans.append(arr[right])
                right += 1
        
        return ans

Time & Space Complexity

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

Where $n$ is the number of nodes in the tree and $k$ is the size of our sliding window

4. Binary Search The Left Bound

Intuition

Since the inorder traversal produces a sorted array and we need a contiguous subarray of size k, we can binary search for the optimal starting position of this window. For any starting position, we compare the distances of the leftmost and rightmost elements in the window to decide if shifting right would improve our answer.

Algorithm

Perform an inorder traversal to get all values in sorted order.
Binary search for the left boundary of the k-element window. The search range is from index 0 to n-k.
At each midpoint, compare the distance of the element at mid with the element at mid+k. If the element at mid+k is closer, shift the window right; otherwise, keep searching left.
Return the subarray starting at the found left boundary with length k.

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(node, arr):
            if not node:
                return
            
            dfs(node.left, arr)
            arr.append(node.val)
            dfs(node.right, arr)
        
        arr = []
        dfs(root, arr)
        
        left = 0
        right = len(arr) - k
        
        while left < right:
            mid = (left + right) // 2
            if abs(target - arr[mid + k]) < abs(target - arr[mid]):
                left = mid + 1
            else:
                right = mid

        return arr[left:left + k]

Time & Space Complexity

Time complexity:
- $O(n)$ in Java
- $O(n+k)$ in Python
Space complexity: $O(n)$

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

5. Build The Window With Deque

Intuition

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.

Algorithm

Perform an inorder traversal of the tree.
Maintain a deque to store the current window of candidates.
For each visited node, append its value to the deque.
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.
Return the elements in the deque as the result.

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)

Time & Space 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

Common Pitfalls

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.

# Wrong: Can cause index -1 access
left = bisect_left(arr, target) - 1  # If target < all elements, left = -1
# Must check: if left < 0 before accessing arr[left]

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.

# Wrong: Min-heap evicts closest values
heappush(heap, (abs(node.val - target), node.val))

# Correct: Max-heap (negate distance) evicts farthest
heappush(heap, (-abs(node.val - target), node.val))

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.