Watch 10 video solutions for Closest Binary Search Tree Value II, a hard level problem involving Two Pointers, Stack, Tree. This walkthrough by Cracking FAANG has 8,016 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]
Example 2:
Input: root = [1], target = 0.000000, k = 1 Output: [1]
Constraints:
n.1 <= k <= n <= 104.0 <= Node.val <= 109-109 <= target <= 109
Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?
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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal + Two Pointers | O(n) | O(n) | Simple implementation when storing all node values is acceptable |
| Max Heap (Size k) | O(n log k) | O(k) | Useful when k is small compared to the number of nodes |
| Two Stack Predecessor/Successor Iterators | O(k + log n) | O(log n) | Optimal solution that leverages BST ordering and avoids full traversal |