Stack-base postorder traversal 2

[mandingo]

is there a way to write a stack-base implementation of postorder traversal of a binary tree without using recursion?<br>
<br>
how do I save the right subtree and the root at the same time while the left subtree is visited?

 

[MikeLacey]

Mandingo - is there some reason you don't want to use recursion?<br>
<br>
Mike<br>
<p>Mike Lacey<br><a href=mailto:Mike_Lacey@Cargill.Com>Mike_Lacey@Cargill.Com</a><br><a href=

http://www.cargill.com/>

Cargill's Corporate Web Site</a><br>

 

[mandingo]

It is an excercise I am doing for a school project. The main idea is to do something that is not of the ordinary.<br>

 

[MikeLacey]

There's a book that might be interesting to you by a man called Knuth &quot;Basic Algorithms&quot; or something close to that.<br>
<br>
It's a well known and popular book despite its age (I have a copy myself) and most computer bookshops should be able to get it for you, <A HREF="

http://www.amazon.com"

TARGET="_new">

http://www.amazon.com</A>

should have it.<br>
<br>
Mike <p>Mike Lacey<br><a href=mailto:Mike_Lacey@Cargill.Com>Mike_Lacey@Cargill.Com</a><br><a href=

http://www.cargill.com/>

Cargill's Corporate Web Site</a><br>

 

[mandingo]

Thanks a million<br>
I guess that is a better idea as I will need info all through the semester.<br>
Thanks

 

[ssingh]

Although , what you are looking for is a very complex method . You can do that using stack also. You've to keep track of the depth of binary tree. OR You 've to remove the subtree you've visited at last. Then according to the logic you will have to fetch the data on the stack. <br>
<br>
For eg. I am writing the Pseudocode.<br>
1) While (root-&gt;left != NULL) root = root-&gt;left.<br>
2) if(root-&gt;right != NULL) root = root-&gt;right. goto step 1;<br>
3) Fetch value root-&gt;value on the stack. <br>
4) Goto step 1;<br>
Repeat the same step unless there is only root there.<br>
<br>
I think this raw Pseudocode will help you.<br>
<br>
Thanx<br>
Siddhartha Singh<br>
<A HREF="mailto:ssingh@aztecsoft.com">ssingh@aztecsoft.com</A>