# Closest Number in Binary Search Tree II

In a binary search tree, find k nodes containing the closest numbers to the given target number. return them in sorted array

**Assumptions:**

* The given root is not null.
* There are no duplicate keys in the binary search tree.

**Examples:**

    5

  /    \\

2      11

     /    \\

    6     14

closest number to 4 is 5

closest number to 10 is 11

closest number to 6 is 6

**Solution:** inorder traversal with queue

A queue of k size to track window of nodes closest

Traverse inorder sums into two situations:

* in order towards the target

Nodes that first entered the queue is the furthest away from target, thus can be eliminated first

* in order away from the target

If new right node are closer to furthest left nodes in window, we can eliminate the furthest left node

```java
public class Solution {
  public int[] closestKValues(TreeNode root, double target, int k) {
    Queue<TreeNode> q = new LinkedList<>();
    inOrder(root, q, k, target);
    int[] result = qtoArr(q, k > q.size() ? q.size() : k);

    return result;
  }

  private void inOrder(TreeNode root, Queue<TreeNode> q, int maxSize, double target){
    if (root == null) return;

    inOrder(root.left, q, maxSize, target);

    if (q.size() == maxSize){
      check(root, q, target);
    } else {
      q.offer(root);
    }

    inOrder(root.right, q , maxSize, target);
  }

  private void check(TreeNode root, Queue<TreeNode> q, double target){
    int topVal = q.peek().key;
    int rootVal = root.key;
    if(Math.abs(rootVal - target) < Math.abs(topVal - target)){
      q.poll();
      q.offer(root);
    }
  }

  private int[] qtoArr(Queue<TreeNode> q, int size){
    int[] result = new int[size];
    for (int i = 0; i < size; i++){
      result[i] = q.poll().key;
    }
    return result;
  }
}
```

TC: O(N) one pass

SC: O(k) k sized queue + O(logN) recursion stack


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/tree-traversal/closest-number-in-binary-search-tree-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.