@Abhishek:
Its not always that you reach a leaf through the node.
But still your logic seems correct.
There would be 3 candidates for minimum:
-->predecessor
-->current node
-->successor.
On Sat, Aug 20, 2011 at 1:13 PM, Abhishek Yadav
<algowithabhis...@gmail.com>wrote:
> 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.
>
--
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.
