K nearest Element in BST

K nearest Element in BST

  July 05, 2022    

---

Idea is to use a queue in inorder fashion which will make sure that the output is in sorted order

If queue size>=k which means we have to chek if first of the queue is not nearer to the current root element then poll from the queue and add current

 

 

 void KnearestElement(Node root, int k, int x, Queue<Integer> q)  {
    if(root == null)
    return ;
    KnearestElement(root.left, k, x, q);
    if(root.data !=x) {
    if(q.size()<k)
    q.add(root.data);
    else if(Math.abs(q.peek()-x)>Math.abs(root.data-x)) {
    q.poll();
    q.add(root.data);
    }}
    KnearestElement(root.right, k, x, q);
    }