@Abhishek:nice algo dude..
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.
