CareerCup

Simple binary search, but we keep track of the last element that was closest to the key we are looking for. It can be recursive or iterative. I'll try recursive.

Public void BinaryCloseSearch(Node, root, Node closest, int data) {
    
    If(root.data == data) { //found the node. 
        Return root;
    }

    Else if(root.left == null && root.right == null). //reached the last leaf node. 
	Return closest;


	//if current node is closer the current closest node, reset the closest node
	if(Math.abs(root.data - data) < Math.abs(closest.data - data) { 
       		Closest = root;
	}

	//standard bst search
	if(root.data < data) {
		Node nodeFound = BinaryClosestSearch(root.right, closest, data);
	Else 
		Node nodeFound = BinaryClosestSearch(root.left, closest, data);
	
	Return nodeFound;
}

int bestCase(struct tree * root,int bestKey)
{
struct tree * rPtr=NULL;
int prevKey=0;
rPtr=root;
if ( NULL == rPtr)
return 0;
while (NULL != rPtr)
{
if ( bestKey == rPtr->key )
{
prevKey= rPtr->key;
break;
}
else if ( bestKey < rPtr->key)
{
if ( NULL == rPtr->left)
break;
prevKey= (abs(rPtr->key - bestKey) < abs(rPtr->left->key - bestKey))? rPtr->key : rPtr->left->key;
rPtr=rPtr->left;
}
else if ( bestKey > rPtr->key)
{
if ( NULL == rPtr->right )
break;
prevKey= (abs(rPtr->key - bestKey) < abs(rPtr->right->key - bestKey))? rPtr->key : rPtr->right->key;
rPtr=rPtr->right;
}

}
return prevKey;
}

void findclosestkey(node *root, int target, int& diff, int& closest) {
   if (root==NULL) return;
   int cur_diff == abs(root->data - target);
   if (cur_diff < diff) {
       diff = cur_diff;
       closest = root->data;
   } 

  if (diff == 0) return;
  else {
          if (target > root->data) 
              findclosestkey(root->right, target,diff,closest);
          else 
              findclosestkey(root->left, target,diff,closest);
   }
}

}

A slightly modified binary search. Here is in Java. Returns the node containing the closest data.


public Node bestLookup(Node root, int n, Node best){
if(root==null) return best;
if(root.data==n) return root;
if(Math.abs(root.data-n)<Math.abs(best.data-n)) best=root;
if(n<root.data) return bestLookup(root.left,n,best);
if(n>root.data) return bestLookup(root.right,n,best);
}

How about doing the search in a way that is non-recursive so the memory cost would be O(1) and not O(log n) ( in addition to a O(log n) runtime complexity ):

public int closest(Node node, int value){
  //find the lower and upper constraints surrounding the searched value
  Integer lower = null;
  Integer upper = null;
  while(node != null){
    //if this is a lower constraint
    if(node.value > value){
      upper = node.value;
      node = node.left;
    }
    //if this is an upper constraint
    else if(node.value < value){
      lower = node.value;
      node = node.right;
    }
    //otherwise this is the value
    else{
      return node.value;
    }
  }

  //return the closest existing constraint
  if(lower != null){
    if(upper != null){
      if( Math.abs(value - lower) < Math.abs(upper - value) ){
        return lower;
      }
      return upper;
    }
    return lower;
  }
  return upper;
}

Or, even using a single 'best' pointer rather than constraints:

public int closest(Node node, int value){
  Integer closest = null;
  int dist = Integer.MAX_VALUE;
  while(node != null){
    int tempDist = Math.abs(value - node.value);
    if(tempDist == 0){
      return node.value;
    }
    if(dist > tempDist){
      dist = tempDist;
      closest = node.value;
    }
    if(node.value > value){
      node = node.left;
    }
    else{
      node = node.right;
    }
  }
  return closest;
}

def closest_key(root):
    bst_itr = BstIterator(root)
    prev_key = sys.maxint
    while bst_itr.has_next():
        node_key = bst_itr.next().key
        if key < node_key:
            break
        prev_key = node_key

    if abs(node_key - key) < abs(prev_key - key):
        closest = node_key
    else:
        closest = prev_key
    return closest