272. Closest Binary Search Tree Value II Solution

The problem

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:

The number of nodes in the tree is n.
1 <= k <= n <= 10⁴.
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?

Approach overview

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.

Solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            if len(q) < k:
                q.append(root.val)
            else:
                if abs(root.val - target) >= abs(q[0] - target):
                    return
                q.popleft()
                q.append(root.val)
            dfs(root.right)

        q = deque()
        dfs(root)
        return list(q)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    private List<Integer> ans;
    private double target;
    private int k;

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        ans = new LinkedList<>();
        this.target = target;
        this.k = k;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (ans.size() < k) {
            ans.add(root.val);
        } else {
            if (Math.abs(root.val - target) >= Math.abs(ans.get(0) - target)) {
                return;
            }
            ans.remove(0);
            ans.add(root.val);
        }
        dfs(root.right);
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    queue<int> q;
    double target;
    int k;

    vector<int> closestKValues(TreeNode* root, double target, int k) {
        this->target = target;
        this->k = k;
        dfs(root);
        vector<int> ans;
        while (!q.empty()) {
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }

    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        if (q.size() < k)
            q.push(root->val);
        else {
            if (abs(root->val - target) >= abs(q.front() - target)) return;
            q.pop();
            q.push(root->val);
        }
        dfs(root->right);
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closestKValues(root *TreeNode, target float64, k int) []int {
	var ans []int
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if len(ans) < k {
			ans = append(ans, root.Val)
		} else {
			if math.Abs(float64(root.Val)-target) >= math.Abs(float64(ans[0])-target) {
				return
			}
			ans = ans[1:]
			ans = append(ans, root.Val)
		}
		dfs(root.Right)
	}
	dfs(root)
	return ans
}

Try this approach in the editor

Complexity analysis

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

Frequently asked questions

Is Closest Binary Search Tree Value II easy or hard?

Closest Binary Search Tree Value II is classified as a Hard problem because it requires combining BST properties with iterator design. The brute force traversal is straightforward, but achieving the optimal O(k + log n) solution with two stacks requires deeper understanding of tree traversal mechanics.

Closest Binary Search Tree Value II Python/Java solution

Python and Java implementations typically use two stacks to track predecessors and successors in the BST. After initializing the stacks from the root relative to the target, repeatedly compare the top elements and pop from the closer side while pushing the next predecessor or successor node.

How to solve Closest Binary Search Tree Value II in O(n)?

Run an inorder traversal of the BST to produce a sorted list of node values. Use binary search to find the position closest to the target, then expand outward with two pointers to pick the k closest elements. The traversal takes O(n) time and the two‑pointer selection takes O(k). Total complexity remains O(n) with O(n) space.

What is the best approach for Closest Binary Search Tree Value II?

The optimal approach uses two stacks to simulate predecessor and successor iterators in the BST. One stack stores nodes less than or equal to the target, and the other stores nodes greater than the target. At each step you compare which stack top is closer to the target and advance that iterator. This runs in O(k + log n) time with O(log n) space.

Is Closest Binary Search Tree Value II asked at Google/Amazon/Meta?

Variants of BST closest value and iterator problems frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of BST ordering, traversal strategies, and how to design efficient iterators using stacks.

What data structure is used in Closest Binary Search Tree Value II?

Common data structures include stacks for predecessor and successor iterators, heaps (priority queues) for maintaining the k closest values, and arrays if using an inorder traversal. The tree itself is a Binary Search Tree, which provides the sorted ordering needed for efficient selection.

What is the time complexity of Closest Binary Search Tree Value II?

The optimal two‑stack iterator solution runs in O(k + log n) time on average because initialization walks down the tree once and each of the k selections advances an iterator along tree edges. Space complexity is O(log n) for the stacks in a balanced BST. Simpler approaches like inorder traversal require O(n) time and space.

Closest Binary Search Tree Value II solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Closest Binary Search Tree Value II solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems