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.

Description Hints 4 Solution Video 14:16

272. Closest Binary Search Tree Value II

Hard61.1% acceptance3 companiesPremium elsewhere, free here

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)?

Asked at 3 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Consider implement these two helper functions:

getPredecessor(N), which returns the next smaller node to N.
getSuccessor(N), which returns the next larger node to N.

Hint 2

Try to assume that each node has a parent pointer, it makes the problem much easier.

Hint 3

Without parent pointer we just need to keep track of the path from the root to the current node using a stack.

Hint 4

You would need two stacks to track the path in finding predecessor and successor node separately.

14:16

Still stuck?Read the written solution, or watch a walkthrough.

Open solution