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

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