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 <[email protected]> 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 <[email protected]>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 <[email protected]> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
