CareerCup

int getNext(node* ptr, int num)
{
int returnvalue=-1;
int currentNext=-1;

while(ptr)
{
if(ptr->data > num)
{
if(ptr->left==null)
{
returnvalue=ptr->data;
}
currentNext=ptr->data;
ptr=ptr->left;
}
else
{
if(ptr->right==null)
{
returnValue=currentNext;
}
ptr=ptr->right;
}
}

return returnValue;
}

A bit complicated then what I wanted, but this should work. Please let me know if there are any issues with it or if someone has a simpler solution


Node * closestToKey(Node * root, int key)
{
Node * temp = root;

if(!root)
return error;

if(!root->left && !root->right)
return root;


while(temp)
{

if(temp->data == key)
return temp;

//Go Right
if(key > temp->data)
{
diff1 = key - temp->data;

if(temp->right)
{
if(temp->right->data > key)
{
diff2 = temp->right->data - key;
}
else
{
diff2 = key - temp->right->data;
}

//Now we have diff1 && diff2, so let's find the
closest between the root of subtree & it's child.

if(diff < diff2)
{
return temp;
}
if(diff1 >= diff2)
{
temp = temp->right;
}
}

//Right child is Null, so return the root of this subtree
else
{
return temp;
}
}

//Do the same as above for left tree
else
{
diff1 = temp->data - key;

if(temp->left)
{
if(temp->left->data > key)
{
diff2 = temp->left->data - key;
}
else
{
diff2 = key - temp->left->data;
}

//Now we have diff1 && diff2, so let's find the closest
between the root of subtree & it's child.
if(diff < diff2)
{
return temp;
}
if(diff1 >= diff2)
{
temp = temp->left;
}
}

//Left child is Null, so return the root of this subtree
else
{
return temp;
}
}
}
}

Here is a solution in Java. Though, I am using a class where key value can be of any data type but the assumption here is is that the key values are integers. Basically, you just need to traverse the tree and see if the difference is closest . If yes then just store it. I have another commented example which was asked to me by Google: the greatest node value of a given key.Both examples work and the code is fairly easy to undrstand. Enjoy!!

int smallestDis=100000000; Key smallestNode;
    public Key findClosestMatch(Key k){
        findClosestMatch(root, k);
        return smallestNode;
    }
    
    private Key findClosestMatch(Node r, Key key){
        
        if (r == null) return null;
        
        int cmp = key.compareTo(r.key);
        //closest match
        int dis=Math.abs(Integer.parseInt(key.toString())-Integer.parseInt(r.key.toString()));
        //greatest element
       // int dis=Integer.parseInt(r.key.toString())-Integer.parseInt(key.toString());
        if (dis>=0 && dis <= smallestDis){
            smallestDis=dis;
            smallestNode=r.key;
        }
        
      
        if (cmp < 0) { 
             
             return findClosestMatch(r.left, key);
             
                
        }
        else if (cmp > 0) {
            return findClosestMatch(r.right, key);

                 
        }
        else
           return r.key;
        
  
        

    }