hard Closest Binary Search Tree Value II

Problem Statement

Given the root of a binary search tree, an integer target, and an integer k, return a 1D array total containing k values from the BST which are closest to the given target value. You may return the answer in any order.

Examples

Example 1:
- Input: BST = [10,5,15,2,7,null,18], target = 8.5, k = 3

Expected Output: [7,10,5]
Justification: The three numbers closest to 8.5 in the BST are 7, 10, and 5.
Example 2:
- Input: BST = [20,10,30,5,15,null,null,3,8,null,17], target = 15.5, k = 2

Expected Output: [15,17]
Justification: The two numbers closest to 15.5 in the BST are 15 and 17.
Example 3:
- Input: BST = [4,2,6,1,3,5,7], target = 4.5, k = 1

Expected Output: [4]
Justification: The number closest to 4.3 in the BST is 4.

Constraints:

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

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Closest Binary Search Tree Value II — problem

0. Pattern family

Family: BST k closest / two stacks or inorder window

1. Why / judgment (K3)

Hard company: k values in BST closest to target. Patterns: (1) inorder → sorted array then two-pointer / sort-by-dist O(n log n); (2) two iterators (predecessors stack + successors) merge O(k+h); (3) maintain window deque of size k during inorder O(n). Standout judgment: exploit BST order — do not treat as unsorted bag only.

2. Worked complexity / derivation (K11)

Inorder+sort by |x-t|: O(n log n) time O(n) space.
Inorder+sliding window on sorted: O(n).
Two-stack merge: O(k + h) after O(h) init; best when k≪n.
Heap of size k over all nodes: O(n log k) ignores BST.

3. Pattern + recognition + when-NOT (K12)

Name: BST K-CLOSEST (window / dual stack)

Recognition: BST + target + k closest values any order.

When-NOT: Closest BST Value I (k=1) → walk tree O(h). Unsorted array k closest → heap/quickselect. k largest values → different order stat.

4. Edge hand-run (K13)

BST [10,5,15,2,7,null,18] t=8.5 k=3 → {5,7,10}.
k=1 → single closest. k=n → all values. target far left → k smallest.

5. Interviewer follow-ups & drills

Q1. Why sorted helps?
Model answer: Closest k form a contiguous segment in sorted order — sliding window on inorder list.

Q2. Two stacks idea?
Model answer: One stack for next smaller (pred), one for next larger (succ); always pick nearer.

Q3. Heap on |val-t|?
Model answer: Correct but O(n log k) and wastes BST structure — weaker interview answer.

✅ Solution Closest Binary Search Tree Value II

Problem Statement

Given the root of a binary search tree, an integer target, and an integer k, return a 1D array containing k values from the BST which are closest to the given target value. You may return the answer in any order.

Examples

Example 1:
- Input: BST = [10,5,15,2,7,null,18], target = 8.5, k = 3

Expected Output: [7,10,5]
Justification: The three numbers closest to 8.5 in the BST are 7, 10, and 5.
Example 2:
- Input: BST = [20,10,30,5,15,null,null,3,8,null,17], target = 15.5, k = 2

Expected Output: [15,17]
Justification: The two numbers closest to 15.5 in the BST are 15 and 17.
Example 3:
- Input: BST = [4,2,6,1,3,5,7], target = 4.5, k = 1

Expected Output: [4]
Justification: The number closest to 4.3 in the BST is 4.

Constraints:

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

Solution

To solve this problem, we begin by leveraging the natural order of binary search trees (BSTs) to find the k values closest to a given target. The key insight here is to use an in-order traversal of the BST, which naturally visits the nodes in ascending order. This methodical approach allows us to access each value within the tree systematically, ensuring that we can compare each value directly against the target. By collecting all values in a list through this traversal, we position ourselves to efficiently determine which values are closest to the target by examining their absolute differences from the target.

Once we have the list of values from the in-order traversal, the next step involves sorting this list based on each value's proximity to the target. This sorting is done by calculating the absolute difference between the target and each value in the list. After sorting, the first k elements of this list represent the closest values to the target. This approach is effective because it combines the inherent ordered nature of the BST with a sorting mechanism that prioritizes closeness to the target.

Step-by-step Algorithm

Initialize: Start by creating a list, values, to store the values of all nodes in the binary search tree (BST).
In-order Traversal:
- Recursively perform an in-order traversal of the BST.
- During the traversal, visit the left child, the node itself, and then the right child in this order.
- Add each node’s value to the values list. This step ensures that the values are stored in sorted order because of the BST’s properties.
Sorting by Proximity:
- After completing the in-order traversal, you will have a list of all node values in sorted order.
- Sort the values list based on the absolute difference from the target value. This rearrangement prioritizes the values closest to the target.
Selecting Closest Values:
- Once the list is sorted by proximity to the target, select the first k elements from this list.
- These k elements are the closest values to the target.
Return the Result:
- Return the sublist containing the closest k values to the target.

Algorithm Walkthrough

Let's consdier the given input:

        20
       /  \
      10  30
     /  \
    5   15
   / \    \
  3   8    17

target = 15.5, and k = 2.

In-order Traversal:
- Start with the root node 20, but since we are doing an in-order traversal, we first move to the left subtree.
- At node 10, again move to the left subtree.
- At node 5, move to its left child 3. Since 3 has no left child, it's the first node to visit.
  - Add 3 to values: [3]
- Back to 5, now visit it.
  - Add 5 to values: [3,5]
- Move to 5's right child 8 and visit it.
  - Add 8 to values: [3,5,8]
- Having visited 5 and its children, go back to 10 and visit it.
  - Add 10 to values: [3,5,8,10]
- Visit 10's right child 15, but since 15 has a right child 17, we first visit 17.
  - Add 15 to values after 17: [3,5,8,10,17,15]
- With the left subtree fully visited, move to the root 20 and visit it.
  - Add 20 to values: [3,5,8,10,15,17,20]
- Finally, visit the right subtree, which is just node 30.
  - Add 30 to values: [3,5,8,10,15,17,20,30]
Sorting by Proximity to Target (15.5):
- Sort values by the absolute difference from 15.5, resulting in [15,17,10,8,20,5,3,30].
Selecting Closest Values (k=2):
- After sorting by proximity, the closest values to 15.5 are 15 and 17.
- Thus, we correctly identify [15,17] as the k=2 closest values to the target.

Code

java

import java.util.*;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  private void inorderTraversal(TreeNode root, List<Integer> values) {
    // Base case: if the node is null, return
    if (root == null) return;
    // Traverse the left subtree
    inorderTraversal(root.left, values);
    // Add the node's value to the list
    values.add(root.val);
    // Traverse the right subtree
    inorderTraversal(root.right, values);
  }

  public List<Integer> closestKValues(TreeNode root, double target, int k) {
    List<Integer> values = new ArrayList<>();
    // Populate the list with the BST values in sorted order
    inorderTraversal(root, values);

    // Sort the list based on the absolute difference with the target
    Collections.sort(values, (a, b) ->
      Double.compare(Math.abs(a - target), Math.abs(b - target))
    );

    // Return the first k elements from the sorted list
    return values.subList(0, k);
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    TreeNode root1 = new TreeNode(10);
    root1.left = new TreeNode(5);
    root1.right = new TreeNode(15);
    root1.left.left = new TreeNode(2);
    root1.left.right = new TreeNode(7);
    root1.right.right = new TreeNode(18);
    System.out.println(solution.closestKValues(root1, 8.5, 3)); // Expected: [7, 10, 5]

    // Example 2
    TreeNode root2 = new TreeNode(20);
    root2.left = new TreeNode(10);
    root2.right = new TreeNode(30);
    root2.left.left = new TreeNode(5);
    root2.left.right = new TreeNode(15);
    root2.left.left.left = new TreeNode(3);
    root2.left.left.right = new TreeNode(8);
    root2.left.right.right = new TreeNode(17);
    System.out.println(solution.closestKValues(root2, 15.5, 2)); // Expected: [15, 17]

    // Example 3
    TreeNode root3 = new TreeNode(4);
    root3.left = new TreeNode(2);
    root3.right = new TreeNode(6);
    root3.left.left = new TreeNode(1);
    root3.left.right = new TreeNode(3);
    root3.right.left = new TreeNode(5);
    root3.right.right = new TreeNode(7);
    System.out.println(solution.closestKValues(root3, 4.5, 1)); // Expected: [4]
  }
}

Complexity Analysis

Time Complexity

In-order Traversal: The in-order traversal of the BST has a time complexity of , where (N) is the number of nodes in the BST. This is because each node in the tree is visited exactly once.
Sorting: After collecting all node values, the list is sorted based on the absolute difference from the target value. The sort operation has a time complexity of in the average and worst case.
Extracting the (k) Closest Values: Extracting the first (k) elements from the sorted list has a time complexity of , which is negligible compared to the sorting step for large (N).

Therefore, the overall time complexity of the solution is due to the sorting step being the most significant factor.

Space Complexity

In-order Traversal Storage: The space complexity is due to the storage of all (N) node values in a list or array.
Recursive Stack Space: In the case of the recursive in-order traversal, there's additional space complexity due to the call stack. However, in a balanced BST, this would be . In the worst case (a completely unbalanced tree), it could be .

🎯 STRICT STANDOUT — Solution Closest Binary Search Tree Value II

0. Pattern family

Family: BST k closest — inorder window / dual stack elevate

1. Why / judgment (K3)

Page may collect inorder then sort by distance O(n log n) — correct but not tight on BST. Standout elevation: (A) inorder sorted list + two pointers expand k-window around target O(n); (B) dual predecessor/successor stacks O(k+h). State that closest k are contiguous in sorted order — the key lemma. Hand-run target 8.5 on [2,5,7,10,15,18].

2. Worked complexity / derivation (K11)

Inorder Θ(n) + sort-by-dist O(n log n) + first k — what naive sol often does.
Inorder + two-pointer window: find insert position of target O(n) then expand O(k) → O(n).
Dual stack: build path O(h), then k steps O(k+h).
Space O(n) array vs O(h) stacks.

3. Pattern + recognition + when-NOT (K12)

Name: K CLOSEST IN SORTED INORDER WINDOW

Recognition: BST property → sorted inorder; k closest contiguous; merge pred/succ.

When-NOT: k=1 walk only comparing abs — Closest BST I. Treat nodes as unordered → heap O(n log k) leaves BST unused. Modify tree structure permanently without restore.

4. Edge hand-run (K13)

Inorder [2,5,7,10,15,18], t=8.5, k=3:
Distances: 6.5,3.5,1.5,1.5,6.5,9.5 → closest 7,10,5 (ties by abs).
Window view: best segment of length 3 minimizes |endpoints-ish| — two pointer from lo/hi.
k=1 →7 or 10 (equal dist — either if allowed).
Empty not allowed n≥k≥1.

5. Interviewer follow-ups & drills

Q1. Prove contiguity of k closest in sorted array
Model answer: If optimal set skips an interior value, swapping the farther endpoint for the interior never increases max distance set cost under absolute deviation selection — standard: k closest form a contiguous subarray.

Q2. Dual stack next()
Model answer: pred stack: next smaller by popping and pushing left spine of right child; succ symmetric.

Q3. When is O(n log n) sort-by-dist acceptable?
Model answer: n small or interviewer wants quick correct; still name O(n)/O(k+h) upgrades.

Q4. Any order output?
Model answer: Problem allows any order — no need to sort answer by value unless asked.

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Closest Binary Search Tree Value II? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Closest Binary Search Tree Value II** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Closest Binary Search Tree Value II** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Closest Binary Search Tree Value II**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Closest Binary Search Tree Value II**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Max Points on a Line Sliding Window Median →