Since we are given pointer to root node, we can easily find the minimum element in the tree.
This will be the first node in the inorder traversal, now use method to find the inorder successor of a each node. Do it iteratively. Complexity will be O(n log n) and O(n) if tree is skewed. Correct me if m wrong. Sanju :) On Tue, Sep 27, 2011 at 8:49 AM, Nitin Garg <nitin.garg.i...@gmail.com>wrote: > Do inorder traversal, to find out the total no. of nodes. > > Next time, do the inorder traversal but keeping the count of nodes visited > and stop when you visit n/2 nodes. > > Non recursive In-order Traversal - > > *inorder*(node) > *while* hasleftchild(node) *do* > node = node.left > *do* > visit(node) > *if* (hasrightchild(node)) *then* > node = node.right > *while* hasleftchild(node) *do* > node = node.left > *else* > *while* node.parent ≠ *null* *and* node == node.parent.right *do* > node = node.parent > node = node.parent > *while* node ≠ *null* > > Source: Wikipedia > > On Tue, Sep 27, 2011 at 9:13 PM, Sanjay Rajpal <srn...@gmail.com> wrote: > >> Recursion also requires space, so the problem is how to traverse >> without extra space. >> >> Once this is done, nothing is left in the problem. >> Sanju >> :) >> >> >> >> On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma < >> dheerajsharma1...@gmail.com> wrote: >> >>> @anshu >>> can middle element can be found if the no. of nodes are not given... >>> >>> >>> On Tue, Sep 27, 2011 at 8:34 PM, vikas <vikas.rastogi2...@gmail.com>wrote: >>> >>>> a simple one is rabit-tortoise method, and using stackless traversal, >>>> facing a lot of corner cases in coding this, can someone check this as >>>> well? >>>> >>>> On Sep 27, 6:41 pm, anshu mishra <anshumishra6...@gmail.com> wrote: >>>> > its not o(n) it is O(max height of tree) :P >>>> > i have not seen the constraint. >>>> >>>> -- >>>> 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. >>>> >>>> >>> >>> >>> -- >>> *Dheeraj Sharma* >>> >>> >>> >>> -- >>> 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. >> > > > > -- > Nitin Garg > > "Personality can open doors, but only Character can keep them open" > > -- > 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.
