No your solution is correct too....its just that in your solution number of
comparisons done with the original number are more, while in my solution
they get down to 2. otherwise complexities of both the solution would be
O(log n).
I am stressing on no. of comparisons because in these kind of questions
where we do compare something no. of comparisons matters.
for example when we talk about finding largest and second largest in an
array, we do try to minimize number of comparisons.
Otherwise your solution is correct no doubt.
On Sat, Aug 20, 2011 at 12:59 PM, Dipankar Patro <dip10c...@gmail.com>wrote:
> is there anything wrong in my algo?
> do tell me.
>
>
> On 20 August 2011 12:56, Abhishek Yadav <algowithabhis...@gmail.com>wrote:
>
>> Hey i tried it now and got to another solution
>> O(log n) solution:
>> 1. try searching for the number , if found,return the node, otherwise, you
>> will ultimately reach a leaf node say 'nd'
>> 2. Now the two candidates for the answer would be
>> 1. TreeSuccessor(nd) 2. TreePredecessor(nd)
>> Now compare the original number with these two and minimum would be the
>> answer.
>>
>> (TreeSuccessor and TreePredecessor are the next and previous node resp. in
>> the Inorder traversal of the tree.)
>>
>> On Sat, Aug 20, 2011 at 12:46 PM, Dipankar Patro <dip10c...@gmail.com>wrote:
>>
>>> 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 <algowithabhis...@gmail.com>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 <sukrandha...@gmail.com
>>>> > 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 <
>>>>> algowithabhis...@gmail.com> 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 <
>>>>>> sukrandha...@gmail.com> 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 <
>>>>>>> algowithabhis...@gmail.com> 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 algogeeks@googlegroups.com.
>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>>>> 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 algogeeks@googlegroups.com.
>>>>>>> To unsubscribe from this group, send email to
>>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>>> 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 algogeeks@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>> 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 algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> 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 algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
