why traverse the whole tree?
at each root keep the difference in a min_diff and min_ele.
if the entered value is less root then move to left or right.
repeat above two until whole tree is checked or min_diff becomes 0.
pseudo code:
min_diff = INF; // global variables
min_ele = 0;
find_min_diff(node *root, int num)
{
if (root == null)
return;
// update the difference
if(abs(root->val - num) < min_diff)
{
min_diff = abs(root->val - num);
min_ele = root->val;
}
if ( min_diff == 0)
return; // search is over
// proceed to next element in tree which might be closer to the num
if ( num < root-> val)
find_min_ele(root->left, num);
else
find_min_ele(root->right, num);
}
^^ Complexity : O(logn)
On 20 August 2011 12:36, Abhishek Yadav <[email protected]> wrote:
> yes, the interviewer said that there is a solution in O(log n)
>
>
> On Sat, Aug 20, 2011 at 12:29 PM, sukran dhawan <[email protected]>wrote:
>
>> ur traversing the tree once so it shud be o(n).does the question demand
>> 0(logn) ?
>>
>> On Sat, Aug 20, 2011 at 12:27 PM, Abhishek Yadav <
>> [email protected]> wrote:
>>
>>> what would be the complexity of your solution O(n) or O(log n)..?
>>>
>>> On Sat, Aug 20, 2011 at 12:19 PM, sukran dhawan <[email protected]
>>> > wrote:
>>>
>>>> traverse bst inorder and each time u encounter a node find the
>>>> difference between the element and given element in question . if the
>>>> absolute difference is minimum after traversing the tree that is the
>>>> element
>>>> . u can getback the element using another element which keeps sign of the
>>>> element so that original element can be obtained from diff
>>>>
>>>> On Sat, Aug 20, 2011 at 12:15 PM, Abhishek Yadav <
>>>> [email protected]> wrote:
>>>>
>>>>> Given a BST and a number, Find the closest node to that number in the
>>>>> BST. Give an algorithm for that.
>>>>> Let there be binary search tree having nodes with values
>>>>> 12,34,64,23,64,25,76,6 and the number given is 28, then the answer
>>>>> would be 25 as it is the closest node.
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected].
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
___________________________________________________________________________________________________________
Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
