Watch 10 video solutions for Closest Binary Search Tree Value II, a hard level problem involving Two Pointers, Stack, Tree. This walkthrough by NeetCodeIO has 23,945 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Overview: Given a binary search tree, a floating‑point target, and an integer k, return the k values in the tree that are closest to the target. The BST property helps you avoid scanning the tree blindly and enables ordered traversal strategies.
Approach 1: Full Inorder Traversal + Sort (O(n log n) time, O(n) space)
Perform an inorder traversal of the BST to collect all node values into an array. Inorder guarantees sorted order for a BST. After collecting values, sort them by their absolute difference from the target using a comparator like abs(val - target). Return the first k elements. This approach is straightforward and works even if you ignore BST structure, but it processes the entire tree and performs an extra sort.
Approach 2: Inorder Traversal with Max Heap (O(n log k) time, O(k) space)
Traverse the tree using depth‑first search. Maintain a max heap of size k where the heap key is the distance from the target. Each time you visit a node, push (distance, value) into the heap. If the heap size exceeds k, remove the element with the largest distance. The heap always stores the k closest values seen so far. This reduces memory compared to storing all nodes and avoids sorting the entire list.
Approach 3: Inorder Sliding Window (O(n) time, O(k) space)
Since an inorder traversal of a binary search tree produces sorted values, you can maintain a sliding window of size k. Append values as you traverse. If the window exceeds k, compare the current value with the first element in the window. If the current value is closer to the target, remove the first element; otherwise stop traversal early because further values will only be farther away. This leverages the sorted order of BST values.
Approach 4: Two Stacks for Predecessors and Successors (O(k + log n) time, O(log n) space)
This is the optimal interview solution. Use two stacks to simulate two iterators: one moving toward predecessors (values ≤ target) and another toward successors (values > target). Initialize both stacks by walking the tree from root, similar to a binary search. Then repeatedly choose the closer value between the top of the predecessor and successor stacks. After selecting one, advance that iterator. This technique is similar to the two-pointer pattern applied to BST iterators and avoids scanning the entire tree. It relies heavily on BST ordering and controlled traversal rather than storing all nodes. You can think of it as two lazy iterators built using stacks from two pointers over the sorted BST sequence.
Recommended for interviews: The two‑stack predecessor/successor approach is what most interviewers expect. It demonstrates understanding of BST traversal, iterator design, and how to exploit ordering to reduce complexity. Showing the heap or inorder approach first is fine, but the optimal stack‑based method proves you can turn BST properties into an efficient O(k + log n) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Inorder Traversal + Sort | O(n log n) | O(n) | Simplest implementation when constraints are small and BST properties are not leveraged |
| Inorder Traversal with Max Heap | O(n log k) | O(k) | When you want to keep only k closest values while scanning the tree |
| Inorder Sliding Window | O(n) | O(k) | Works well because inorder traversal produces sorted values |
| Two Stacks (Predecessor + Successor Iterators) | O(k + log n) | O(log n) | Optimal approach that leverages BST ordering and avoids visiting every node |
