Re: [algogeeks] Flatten a BST to produce inorder traversal

[Anantha Krishnan]

Here is the modified version of Morris inorder tree traversal
algorithm


inordermorrisiterative(Tnode *root) {
Tnode *current = root, *pred = NULL, *succesor = NULL;

while (current != NULL) {
succesor = current->right;
if (succesor != NULL && current->next==NULL) {
while (succesor->left != NULL) {
succesor = succesor->left;
}
current->next = succesor;
}
if (current->left == NULL) {
printf(" %d ", current->data);
current = current->right;
} else {
pred = current->left;
while (pred->right != NULL && pred->right != current) {
pred = pred->right;
}

if (pred->right == NULL) {
pred->next = current;
pred->right = current;
current = current->left;
} else {
pred->right = NULL;
printf(" %d ", current->data);
current = current->right;
}
}
}}


You can find my complete code here .

Thanks & Regards
Anantha Krishnan


On Tue, Jul 5, 2011 at 7:52 AM, Ashish Goel  wrote:

> convert BST into DLL
>
> refer stanford tree recursion problem
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta wrote:
>
>> Tree has an extra pointer "next" apart from left and right. Objective
>> is to set next pointer to point to node successor in the tree.
>> Following the next pointer, we would be able to produce sorted list.
>>
>> Looking for both a recursive and non-recursive approach.
>>
>> --Navneet
>>
>> --
>> 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.
>

-- 
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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[Ashish Goel]

convert BST into DLL

refer stanford tree recursion problem

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta wrote:

> Tree has an extra pointer "next" apart from left and right. Objective
> is to set next pointer to point to node successor in the tree.
> Following the next pointer, we would be able to produce sorted list.
>
> Looking for both a recursive and non-recursive approach.
>
> --Navneet
>
> --
> 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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[Piyush Sinha]

U only mentioned in ur question that we have to use "next" pointer to
connect the nodes...while TBT used the left and right pointers

On 7/5/11, Piyush Sinha  wrote:
> I know its not about the traversali just suggested that one can
> use the trick used by Morris traversal to locate the next node of the
> inorder traversal...
>
> On 7/4/11, Navneet Gupta  wrote:
>> @Piyush, it is not about the traversal, you actually have to establish
>> those links such that once they are established, inorder traversal
>> would be just like traversing a list.
>>
>> @Sunny - thanks, exactly what i was looking for
>>
>> On Mon, Jul 4, 2011 at 11:45 PM, Piyush Sinha 
>> wrote:
>>> http://geeksforgeeks.org/?p=6358
>>>
>>> On 7/4/11, Piyush Sinha  wrote:
 Use the concept used in Morris traversal (same as TBT concept)...



 On 7/4/11, sunny agrawal  wrote:
> I think Threaded Binary Tree solves your Problem
> see this 
>
> On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta
> wrote:
>
>> Tree has an extra pointer "next" apart from left and right. Objective
>> is to set next pointer to point to node successor in the tree.
>> Following the next pointer, we would be able to produce sorted list.
>>
>> Looking for both a recursive and non-recursive approach.
>>
>> --Navneet
>>
>> --
>> 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.
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
> --
> 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.
>
>


 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/profile.php?id=10655377926 *

>>>
>>>
>>> --
>>> *Piyush Sinha*
>>> *IIIT, Allahabad*
>>> *+91-8792136657*
>>> *+91-7483122727*
>>> *https://www.facebook.com/profile.php?id=10655377926 *
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>>
>> --
>> Navneet
>>
>> --
>> 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.
>>
>>
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[Piyush Sinha]

I know its not about the traversali just suggested that one can
use the trick used by Morris traversal to locate the next node of the
inorder traversal...

On 7/4/11, Navneet Gupta  wrote:
> @Piyush, it is not about the traversal, you actually have to establish
> those links such that once they are established, inorder traversal
> would be just like traversing a list.
>
> @Sunny - thanks, exactly what i was looking for
>
> On Mon, Jul 4, 2011 at 11:45 PM, Piyush Sinha 
> wrote:
>> http://geeksforgeeks.org/?p=6358
>>
>> On 7/4/11, Piyush Sinha  wrote:
>>> Use the concept used in Morris traversal (same as TBT concept)...
>>>
>>>
>>>
>>> On 7/4/11, sunny agrawal  wrote:
 I think Threaded Binary Tree solves your Problem
 see this 

 On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta
 wrote:

> Tree has an extra pointer "next" apart from left and right. Objective
> is to set next pointer to point to node successor in the tree.
> Following the next pointer, we would be able to produce sorted list.
>
> Looking for both a recursive and non-recursive approach.
>
> --Navneet
>
> --
> 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.
>
>


 --
 Sunny Aggrawal
 B-Tech IV year,CSI
 Indian Institute Of Technology,Roorkee

 --
 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.


>>>
>>>
>>> --
>>> *Piyush Sinha*
>>> *IIIT, Allahabad*
>>> *+91-8792136657*
>>> *+91-7483122727*
>>> *https://www.facebook.com/profile.php?id=10655377926 *
>>>
>>
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/profile.php?id=10655377926 *
>>
>> --
>> 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.
>>
>>
>
>
>
> --
> Navneet
>
> --
> 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.
>
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[Navneet Gupta]

@Piyush, it is not about the traversal, you actually have to establish
those links such that once they are established, inorder traversal
would be just like traversing a list.

@Sunny - thanks, exactly what i was looking for

On Mon, Jul 4, 2011 at 11:45 PM, Piyush Sinha  wrote:
> http://geeksforgeeks.org/?p=6358
>
> On 7/4/11, Piyush Sinha  wrote:
>> Use the concept used in Morris traversal (same as TBT concept)...
>>
>>
>>
>> On 7/4/11, sunny agrawal  wrote:
>>> I think Threaded Binary Tree solves your Problem
>>> see this 
>>>
>>> On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta
>>> wrote:
>>>
 Tree has an extra pointer "next" apart from left and right. Objective
 is to set next pointer to point to node successor in the tree.
 Following the next pointer, we would be able to produce sorted list.

 Looking for both a recursive and non-recursive approach.

 --Navneet

 --
 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.


>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B-Tech IV year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/profile.php?id=10655377926 *
>>
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>
> --
> 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.
>
>



-- 
Navneet

-- 
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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[Piyush Sinha]

http://geeksforgeeks.org/?p=6358

On 7/4/11, Piyush Sinha  wrote:
> Use the concept used in Morris traversal (same as TBT concept)...
>
>
>
> On 7/4/11, sunny agrawal  wrote:
>> I think Threaded Binary Tree solves your Problem
>> see this 
>>
>> On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta
>> wrote:
>>
>>> Tree has an extra pointer "next" apart from left and right. Objective
>>> is to set next pointer to point to node successor in the tree.
>>> Following the next pointer, we would be able to produce sorted list.
>>>
>>> Looking for both a recursive and non-recursive approach.
>>>
>>> --Navneet
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>> --
>> 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.
>>
>>
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-8792136657*
> *+91-7483122727*
> *https://www.facebook.com/profile.php?id=10655377926 *
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[Piyush Sinha]

Use the concept used in Morris traversal (same as TBT concept)...



On 7/4/11, sunny agrawal  wrote:
> I think Threaded Binary Tree solves your Problem
> see this 
>
> On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta wrote:
>
>> Tree has an extra pointer "next" apart from left and right. Objective
>> is to set next pointer to point to node successor in the tree.
>> Following the next pointer, we would be able to produce sorted list.
>>
>> Looking for both a recursive and non-recursive approach.
>>
>> --Navneet
>>
>> --
>> 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.
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
> --
> 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.
>
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
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.

Re: [algogeeks] Flatten a BST to produce inorder traversal

[sunny agrawal]

I think Threaded Binary Tree solves your Problem
see this 

On Mon, Jul 4, 2011 at 11:34 PM, Navneet Gupta wrote:

> Tree has an extra pointer "next" apart from left and right. Objective
> is to set next pointer to point to node successor in the tree.
> Following the next pointer, we would be able to produce sorted list.
>
> Looking for both a recursive and non-recursive approach.
>
> --Navneet
>
> --
> 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.
>
>


-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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.