It seems Dipankar Algo is appropriate at this point of time.
each time successor and predecessor check needs to be done at each
node and the value need to be updated, This is O(log n) approach
because once we check, we move into particular direction.
On Aug 21, 4:59 pm, rahul aravind <rahularavin...@gmail.com> wrote:
> @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.
