Microsoft Interview Question
Software Engineer in TestsTeam: SCVMM (Server tools)
Country: United States
I think the last line should be changed as
if(elem-smaller<bigger-elem)
return smaller;
else
return bigger;
the above code will work for negatives also, the only issues in that is compare abs( currentnumber - minNum ) & abs (currentnumber-MaxNumber) and take the one which gives the minimum.
Analysis is that, nearest number for any node would be left + rightmost and bigger number is Parent Or right-left most { remember this is what you use for deletion }
Traverse to the node, with a parent pointer all along.
then when node is found. break out of the loop
one broken out of the loop you should compare (parent-currentnode, right + left mostt-currentnode, left + right most t-currentnode)... which ever is the minimum you take the corresponding element
where
static BinaryTreeNode<Integer> closest(BinaryTreeNode<Integer> node, BinaryTreeNode<Integer> prevClosest, int n){
if(node == null)
return prevClosest;
BinaryTreeNode<Integer> newClosest = prevClosest;
if( Math.abs(node.data - n) < Math.abs(prevClosest.data - n) ){
newClosest = node;
}
if(node.data < n ){
return closest(node.right, newClosest, n);
}
else{
return closest(node.left, newClosest, n);
}
}
int returnClosest(node *root, int elem)
- jobHunter September 07, 2011{
node *curr=root;
int smaller=-1,bigger=99999;
while(curr){
if(curr->data < elem){
smaller=curr;
curr=curr->right;
}
else if(curr->data > elem){
bigger=curr;
curr=curr->left;
}
else //equals
return curr->data;
} //end of while
return min(elem-smaller,bigger-elem);
}