Closest Binary Search Tree Value II - Solution & Explanation

Problem Overview: Given the root of a binary search tree, a floating‑point target, and an integer k, return the k values in the BST that are closest to the target. The BST property helps narrow the search, but the challenge is efficiently selecting the k closest values without scanning the tree repeatedly.

Approach 1: Inorder Traversal + Two Pointers (O(n) time, O(n) space)

Perform an inorder traversal using depth‑first search. Because it is a BST, the inorder traversal produces a sorted array of node values. Once you have the sorted list, locate the position closest to the target using binary search, then expand outward with two pointers. At each step compare the distance of the left and right values to the target and select the closer one until k elements are collected. This approach is straightforward and easy to implement but requires storing the entire traversal.

Approach 2: Max Heap of Size k (O(n log k) time, O(k) space)

Traverse the tree with DFS and maintain a max heap storing the k closest values seen so far. Each heap entry stores the absolute difference from the target and the node value. When the heap grows beyond size k, remove the farthest element. Using a heap (priority queue) ensures the structure always contains the current best candidates. This method avoids building a full sorted list and is useful when k is small relative to the number of nodes.

Approach 3: Two Stack Iterators (Optimal) (O(k + log n) time average, O(log n) space)

The most efficient method leverages the BST structure directly. Build two stacks representing predecessors (values ≤ target) and successors (values > target). Each stack simulates an inorder iterator moving backward or forward. Initialize them by walking the tree from the root and pushing nodes that could produce predecessors or successors. Then repeatedly compare the top of both stacks and pick the value closer to the target. After selecting one, advance that iterator to the next predecessor or successor. Because each step only moves along tree paths, the algorithm runs in roughly O(k + log n) time.

Recommended for interviews: The two‑stack predecessor/successor technique is the solution most interviewers expect. It demonstrates understanding of BST ordering and iterator design. Starting with the inorder + two pointers method shows solid reasoning, but the stack iterator approach proves you can exploit tree structure for better asymptotic performance.