@Karthikeyan : thanks for the reminder.i totally forgot about Morris
traversal..
i tried to tweak the code provided here :
http://www.geeksforgeeks.org/archives/6358
This will meets the constraints , here is the code:-
http://ideone.com/yp0jI
unfortunately there is one thing which i am not
@all: Now the problem is for getting O(n) time and O(1) space we have to
run two inorder traversal simultaneously. How can we do it??
On Mon, Sep 3, 2012 at 9:31 PM, Karthikeyan V.B wrote:
> @navin and @atul:
>
> inorder traversal without recursion and stack can be done using Morris
> traversal
@navin and @atul:
inorder traversal without recursion and stack can be done using Morris
traversal in O(1) space.
Refer the following link for Morris traversal
http://www.geeksforgeeks.org/archives/6358
now the problem takes O(n) time and O(1) space.
--
You received this message because you a
@navin : if O(n) recursive stack is not allowed then i wonder how can
it can be solved.
On 9/3/12, Navin Kumar wrote:
> @all: If we are doing inorder traversal , it will automatically take O(n)
> space for internal stack.
>
> On Mon, Sep 3, 2012 at 5:17 PM, atul anand wrote:
>
>> @ashish : i.e i
@all: If we are doing inorder traversal , it will automatically take O(n)
space for internal stack.
On Mon, Sep 3, 2012 at 5:17 PM, atul anand wrote:
> @ashish : i.e in decreasing order
>
> inorder(root)
>if not null
> inorder(root->right);
> inorder(root->left);
>
>
> On M
@ashish : i.e in decreasing order
inorder(root)
if not null
inorder(root->right);
inorder(root->left);
On Mon, Sep 3, 2012 at 4:35 PM, Rahul Kumar Patle wrote:
> @dave same doubt as @atul, how we can manage both function parallel
> and to all can we traverse a tree using so
@dave same doubt as @atul, how we can manage both function parallel
and to all can we traverse a tree using some looping instead of traditional
recursive methods..??
On Mon, Sep 3, 2012 at 1:13 PM, atul anand wrote:
> @Dave : algo seems fine...but it seems to me that it would difficult to
> main
what is right to left inorder?
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Sep 3, 2012 at 1:13 PM, atul anand wrote:
> @Dave : algo seems fine...but it seems to me that it would difficult to
> maintain both left to right and right to le
@Dave : algo seems fine...but it seems to me that it would difficult to
maintain both left to right and right to left parallel way :( :( .
it would be gr8 if you can provided little bit of coded algorithm for it.
On Mon, Sep 3, 2012 at 10:36 AM, Dave wrote:
> @Atul007: No need to destroy the BST
@Atul007: No need to destroy the BST. Perform two simultaneous inorder
traversals of the BST, one from left to right (the usual direction) and one
from right to left. At any stage you have selected two nodes. If the sum is
less than the given number, advance the left-to-right traversal; If the s
convert BST to sorted DLL..
now it is a double linked list , so we can find 2 number in O(n) time by
keeping 2 pointers(one at start and one at end) from sorted DLL.
now convert DLL to BST.
On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar wrote:
>
> --
> You received this message because you are sub
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/aLuPUOKxmaoJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this gro
12 matches
Mail list logo
