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
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 tr
@atul anand : actually i was storing the inorder in a seperate array and
then was checking whether it was in inceasing order(like the very first
post in this thread).. hence extra space...
To avoid that, i tried another approach of maitaining a prev pointer and
comparing it with current node and g
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 succ
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Fri, Nov 9, 2012 at 10:00 AM, atul anand wrote:
> @saurabh : correct..yes if you are considering recursive approach , so it
> will take O(n) space stack.But same can be done using Morris traversal then
> spa
@saurabh : correct..yes if you are considering recursive approach , so it
will take O(n) space stack.But same can be done using Morris traversal then
space will be constant.
On Fri, Nov 9, 2012 at 7:40 AM, saurabh singh wrote:
> ^ To perform inorder traversal in a binary tree without using stac
^ 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
blog:geekinessthecoolway.blogs
@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 wrote:
> yes ofcourse... dats the easiest i suppose...
> but in one of my inter
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 curren
@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
current
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 chec
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
12 matches
Mail list logo
