how come the complexity of Morris Traversal is linear, O(n). Any explanation ? or some link ?
On Thu, Nov 8, 2012 at 4:34 PM, Kailash Bagaria <kbkailashbaga...@gmail.com>wrote: > If extra space is not allowed to store the inorder traversal then Morris > Traversal can be used. > Using Morris Traversal, we can traverse the tree without using stack and > recursion. The idea of Morris Traversal > is based on Threaded Binary Tree. In this traversal, we first create links > to Inorder successor and print the data > using these links, and finally revert the changes to restore original > tree.Although the tree is modified through the traversal, it is reverted > back to its original shape after the completion. > Unlike Stack based traversal, no extra space is required for this > traversal. > Once we are able to traverse the tree in inorder manner then we can easily > check if it is BST or not.(By checking the non-decreasing behavior) > For more information on Morris traversal you can visi: > http://www.geeksforgeeks.org/archives/6358 > > > On Wed, Nov 7, 2012 at 10:09 AM, atul anand <atul.87fri...@gmail.com>wrote: > >> @vaibhav : by not using extra space...i guess you mean that you were not >> allowed to use one extra pointer.bcozz space complexity will remain >> constant for inorder approch. >> >> On Tue, Nov 6, 2012 at 1:07 AM, vaibhav shukla >> <vaibhav200...@gmail.com>wrote: >> >>> yes ofcourse... dats the easiest i suppose... >>> but in one of my interviews, i told this approach, but was then asked >>> not to use space (which i was ,to store inorder) >>> So for such cases, you must try other approaches as well. (DO >>> inorder,keep track of previously visited node and compare it with current >>> node for value greater,or less accordingly.) >>> >>> >>> On Tue, Nov 6, 2012 at 12:34 AM, shady <sinv...@gmail.com> wrote: >>> >>>> Hi, >>>> Can we check this by just doing an inorder traversal, and then checking >>>> if it is in increasing order or not ? >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> best wishes!! >>> Vaibhav >>> >>> -- >>> 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. >> > > > > -- > > -- > > ‘Kailash Bagaria’ > B-tech 4th year > Computer Science & Engineering > Indian Institute of Technology, Roorkee > Roorkee, India (247667) > > -- > 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. > --
