Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Nov 9, 2012 at 10:00 AM, atul anand atul.87fri...@gmail.com wrote:
@saurabh : correct..yes if you are considering recursive approach , so it
will take O(n) space stack.But same can be done using
^ To perform inorder traversal in a binary tree without using stack space
the tree must be mutable. In other cases as far as I can think the space
complexity should be asymptotically O(n) where n are the number of nodes.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
@vishal : as discussed in previous post , your solution wont work for
certain test cases...and i dont think so , checking tree in inorder way is
complex .It is simple to implement , you just need to call tree recursively
in Inorder way and keep track of prev node and compare prev node with
I totally agree with atul007.
And that's optimal because one must check every node for
checking whether the tree is a BST or not, and this algorithm
visits each node exactly once.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this
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
@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.comwrote:
yes ofcourse... dats the easiest i suppose...
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
hi all,
yes you can do it that way, but the thing is why are you increasing the
complexity of the problem by again checking the inorder traversal output to
be checked for increasing order.
just traverse through the ones recursively(as we do it in the inoder
traversal) through all the nodes and
