Finding k th closest element in Binary search tree

Question

Here is one question which was asked during my interview . For a given BST find the kth closest element. Traversing the entire tree is unacceptable. Solution should not be o(n) and the space complexity is not an issue. Thanks.

My attempts - Traverse one of the branches of tree to get possible elements and then traverse the branches starting at these elements.

Answer 1

I guess the question was about finding the K-th closest element of a BST to a value V,

Note : it's not possible to do this in less than O(n) time , unless the BST is balanced ,

To find the K-th closest element : We maintain K integers which have been the closest values to V so far , 1.Visiting each node (starting from the root) , we add value of the node , value of its predecessor and successor to the closest values seen so far. (we only put a value into the array close to V, if the array is full. we replace the largest one with this value)

2.We choose the right branch , if successor of the current node is closer to V and left branch if the predecessor is closer.

3.We repeat until there's no more node to visit (we get to a leaf)

4.Time complexity : O(n^2 * k) , if we assume that k is constant (e.g. k = 3) and tree is balanced , the time complexity would be : O(log(n) ^ 2)

Integer[] closest = new Integer[3]; // initialized with null  
void find_3rd_closest(Node current , int K){

    Node succ = Successor(current);
    Node pred = Predecessor(current);

    insert(closest , current.val , K);
    if (succ != null)
        insert(closest , succ.val , K);
    if (pred != null)
        insert(closest , pred.val , K);

    if (succ != null && pred != null)
        if (Math.abs(pred.val - K) < Math.abs(succ.val - K))
            find_3rd_closest(pred , K);
        else
            find_3rd_closest(succ , K);
    else if (pred != null)
        find_3rd_closest(pred , K);
    else if (succ != null)
        find_3rd_closest(succ , K);
    else
        return;
}

void insert(int[] closest , int val, int K){
    for (int i = 0 ; i < closest.length ; i++){
        if (closest[i] != null && Math.abs(K - val) < Math.abs(K - closest[i])){
            for (int j = i ; i < closest.length - 1 ; i++){
                int temp = closest[i+1];
                closest[i+1] = closest[i];
                closest[i] = temp;
            }
        }
        closest[i] = succ.value;
    }
}

Node Successor(Node current){
    if (current.rightChild == null)
        return null;
    current = current.rightChild;
    while (current.leftChild != null)
        current = current.leftChild;
    return current;
}

Node Predecessor(Node current){
    if (current.leftChild == null)
        return null;
    current = current.leftChild;
    while (current.rigthChild != null)
        current = current.rightChild;
    return current;
}

Answer 2

First what we have to find. 1, First you have to get the node ( from the BST root) 2. You have to get the nodes which are below it and distant k. 3. You have to get an ancestor which is k node above it. 4. you have to get the nodes which are kth distant from it. ( in same level or in other level)

                                    A(8) 
                                /         \
                              B(6)           C(22)
                           /    \         /  \
                         D(5)    E(7)   F(17) G(26)
                                      /  \      \
                                  (15)H   I(19)     N(29)
                                    /      \
                              (14) K        L(20)

Okie consider the tree is a BST Tree( A,B,C d are not in sequence of BST, * consider them node reference to identity the node rather than value *) I have attatched a numbers which does represent values.

One more consideration. Since it is declared it a BST Tree. no parent pointers are present.*

You are given root A , of the tree. given a number 17 , and given a value of k=2. First for number 17 get the reference ( F) For k=2 , that is from 2 node distance get all nodes of the tree from F. as decedents of F you have to detect K(14) and L(20) as ascendent of F you have to get Node A. again you have to get Node G( 2 node distance) ( though there is no parent pointer you have to get it).

Step by step 1 first for the number -> 17 get the reference F ( root you have ) do a simple binary search.

ArrayList get_it( Node root_node, int number) {
    node = root_node; 
    if (node ==null)
        throw new IllegarArgumentException("null root node");
    ArrayList  pathtracker = new ArrayList();
    //is the root node matches 
    pathtracker.add(node);  // fix
    if( node.data=number) // fix
    return pathtracker; 
    while(node !=null) {
        if ( node.data==number){
           return pathtracker;
        }
        if ( node.data >= number ){
            node=node.left;
        }
        else{
            node=node.right;
        }
        pathtracker.add(node);        
    } // end of while loop
    return new ArrayList(); //search failed node is not present.
   // returning empty arrayList
 }

now we will use the pathtracker. This has the track nodes from root to this node. 0th node is root, length()-1 th node is the node we have searched for.

for ( int i = pathtracker.length() - 1 , depth=k ;
         ( depth => 0 && i => 0 ) ; i--,depth-- ){  
    if ( i == pathtracker.length() - 1) {//first case
        printnodeDistancek( pathtracker.get(i), depth);
    }else {
        if( pathtracker.get(i).left ! = pathtracker.get(i+1) ){
            printnodeDistancek( pathtracker.get(i).left, depth);
        }else{
            printnodeDistancek( pathtracker.get(i).right, depth);
        }       
    } // end of else block
} // end of loop

void printnodeDistancek( node n, k) {
    if (node==null)
      return;
    if ( k = 0) {
      print node.data;
      return;
    }
    printnodeDistancek( n.left, k-1);
    printodeDistanceK( node.right, k-1);
}

Number given is 17(F node) and Now if k=3 this should print N and B. if K=4 this should print D(5) and E97)

Answer 3

I'll assume closeness between two nodes is defined by the number of edges between them and to resolve the ambiguity ill also assume that in case of equal distance parent is closest then right node then left node.

kth closest element for root node will be kth element is the level order traversal of the tree.

For any Node in tree, we will start with nodes at distance one edge ie its parent, right, left, then distance 2 edge ie parent, right , left of nodes at distance 1 and so on. we will keep counting till we reach k nodes, also make sure we do not count a node twice. consider the following pseudo code.

KthClosest(Node * node, k)
{
    std::queue<Node *> queue;
    std::map<Node *, bool> mapToCheckIFNodeIsCounted;
    int count = 0;
    queue.push_back(node);
    while(count <k)
     {
       Node* node = queue.pop();
       if(node ->parent != NULL)
       {
          if(mapToCheckIFNodeIsCounted.find(node->parent) ==mapToCheckIFNodeIsCounted.end())
            {
              queue->push_back(node->parent);
              mapToCheckIFNodeIsCounted.insert(std::pair<node->parent,true>);

            }
        }
        if(node -> right != NULL)
        {

           if(mapToCheckIFNodeIsCounted.find(node->right) == mapToCheckIFNodeIsCounted.end())
           {
             queue->push_back(node->right);
            mapToCheckIFNodeIsCounted.insert(std::pair<node->right,true>);
           }
        }
        if(node -> left != NULL)
        {

             if(mapToCheckIFNodeIsCounted.find(node->parent) == mapToCheckIFNodeIsCounted.end())
            {
               queue->push_back(node->left);

               mapToCheckIFNodeIsCounted.insert(std::pair<node->left,true>);
            }
       }
       count++;

    }

   // Kth node is the node in queue after loop has finished fraversing k closest elements

   Node *node = queue.pop();
   print(node->value);



}