@atul yes sure why not...
On Sat, Aug 20, 2011 at 1:39 PM, Naman Mahor <naman.ma...@gmail.com> wrote:
> i think there will be three candidate..
> 1. TreeSuccessor(nd) 2. TreePredecessor(nd) 3. nd it self.
>
>
> On Sat, Aug 20, 2011 at 12:56 PM, 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.
>>
>
> --
> 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.
