Closest Binary Search Tree Value II — Inorder + Two Pointer in O(n)

Problem Statement#

Given the root of a BST, a target value target, and integer k, return the k values in the BST closest to target. The answer may be returned in any order.

Constraints:

• 1 <= k <= n <= 10^4
• -10^9 <= Node.val <= 10^9
• -10^9 <= target <= 10^9
• The BST is guaranteed valid

Input:  root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4, 3]

Input:  root = [1], target = 0.0, k = 1
Output: [1]

Why This Problem Matters#

LeetCode 272 "Closest Binary Search Tree Value II" is a classic Google onsite question and shows up in Meta and Amazon interviews. It tests two skills at once: extracting BST order via inorder traversal, and applying a two-pointer technique on a sorted array. Variants include returning values strictly less than target, k closest in a stream, and k closest in a balanced BST in O(k log n).

This problem signals to the interviewer that you understand BST invariants ("inorder is sorted") and can compose them with classic array techniques. Many candidates over-engineer with two stacks for predecessor/successor — a working but harder-to-implement O(k log n) approach. The two-pointer solution is cleaner and gets you to the answer faster on the whiteboard.

The Core Insight#

A BST inorder traversal yields a sorted array. Once we have a sorted array nums, the k values closest to target form a contiguous window of size k in nums. Why contiguous? Because if we picked a non-contiguous subset, swapping the farther element for any closer element inside the gap would always reduce total distance.

So the algorithm is: do an inorder walk to flatten the BST to a sorted list, then shrink from both ends. While the window size exceeds k, remove whichever endpoint is farther from target. The remaining k elements are the answer.

This runs in O(n) time and O(n) space because we touch every node once during inorder, and the two-pointer phase costs at most n - k removals.

Visual Dry Run#

Tree [4,2,5,1,3], target 3.714, k=2.

Solution (Optimal)#

class Solution:
    def closestKValues(self, root, target, k):
        nums = []
 
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            nums.append(node.val)
            inorder(node.right)
 
        inorder(root)
 
        left, right = 0, len(nums) - 1
        while right - left + 1 > k:
            if abs(nums[left] - target) > abs(nums[right] - target):
                left += 1
            else:
                right -= 1
        return nums[left:right + 1]

var closestKValues = function(root, target, k) {
    const nums = [];
    const inorder = (node) => {
        if (!node) return;
        inorder(node.left);
        nums.push(node.val);
        inorder(node.right);
    };
    inorder(root);
 
    let left = 0, right = nums.length - 1;
    while (right - left + 1 > k) {
        if (Math.abs(nums[left] - target) > Math.abs(nums[right] - target)) {
            left++;
        } else {
            right--;
        }
    }
    return nums.slice(left, right + 1);
};

Time: O(n) — one inorder pass plus at most n - k pointer moves. Space: O(n) — the flattened array dominates; recursion stack is O(h).

Common Mistakes#

• Using a max-heap of size k on (distance, val): works but is O(n log k), not optimal.
• Forgetting that inorder of a BST is sorted and trying to sort the array again.
• Comparing nums[left] < nums[right] instead of comparing absolute distances to target.
• Off-by-one when slicing: window length must equal k exactly.
• Using >= instead of > in the distance comparison can drop the wrong endpoint when distances tie.

Interview Tips#

• State the invariant first: "BST inorder is sorted, so the answer is a contiguous window."
• Ask whether the BST is balanced. If yes, mention the O(k log n) two-stack predecessor/successor approach as a follow-up.
• Mention the trade-off: O(n) two-pointer is simpler to code; O(k log n) is better when k is much smaller than n.
• Walk through the dry run before coding — the shrink rule is easy to invert under pressure.

Follow-up Questions#

• Stream version: values arrive online, you cannot store all of them. Hint: use a max-heap of size k keyed on distance.
• Balanced BST in O(k log n): maintain two stacks for predecessors and successors of target. Hint: simulate inorder forward and reverse iterators.
• Strictly less than target: restrict search to the left subtree once you find target. Hint: BST search with bookkeeping.
• k closest with duplicates: allow duplicate values; ensure the window correctly counts multiplicity. Hint: keep raw indices.
• k farthest from target: flip the comparison; answer is at the two ends, not contiguous. Hint: consider both ends as candidates.

Key Takeaways#

• LeetCode 272 is Hard but reduces to inorder traversal plus two pointers.
• Inorder of a BST always yields a sorted sequence — internalize this invariant.
• The k closest values in a sorted array form a contiguous window of length k.
• The shrink rule: drop whichever endpoint has greater absolute distance from the target.
• O(n) time, O(n) space is optimal when you must materialize the inorder list.
• The two-stack predecessor/successor approach achieves O(k log n) on balanced BSTs.
• Frequently asked at Google, Meta, and Amazon for senior tree/BST rounds.