postorder traversal of binary search tree without recursion

[nishit.gupta]

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.
thnx

[Ian Collins]

ni**********@st.com wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.

What have you tried?

--
Ian Collins.

[nishit.gupta]

for inorder
do{
while(p is not equal to NULL){
push it on stack
p = p->left
}
pop(s)
print info(p)
p=p->right
}while(!empty(s))

for preorder it needs little modification.
But i think for post order tree structure should be modified with a
flag comtaining info that node has right or left child or both!
but m not able to think how to proceed???
Ian Collins wrote:

ni**********@st.com wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.

What have you tried?

--
Ian Collins.

[nishit.gupta]

[e-mail] wrote:

for inorder
do{
while(p is not equal to NULL){
push it on stack
p = p->left
}
pop(s)
print info(p)
p=p->right
}while(!empty(s))

for preorder it needs little modification.
But i think for post order tree structure should be modified with a
flag comtaining info that node has right or left child or both!
but m not able to think how to proceed???
Ian Collins wrote:

ni**********@st.com wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.

What have you tried?

--
Ian Collins.

ohh sorry for top post!!

[Nick Keighley]

On 19 Apr, 07:40, [e-mail] wrote:

Can somebody please help me for algorithm for postorder Â*bst traversal
without recursion.
It should use stack. i am not able to implement it.

from wiki:

postorder(node)
if node.left â‰* null then postorder(node.left)
if node.right â‰* null then postorder(node.right)
print node.value

this took me about 10s to find
--
Nick Keighley

[saki]

On Apr 19, 2:01 pm, Nick Keighley <[e-mail]>
wrote:

On 19 Apr, 07:40, [e-mail] wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.

from wiki:

postorder(node)
if node.left â‰* null then postorder(node.left)
if node.right â‰* null then postorder(node.right)
print node.value

this took me about 10s to find

--
Nick Keighley

but this is done by recursion.
the problem here is to do it without recursion.

[nishit.gupta]

Nick Keighley wrote:

On 19 Apr, 07:40, [e-mail] wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.

from wiki:

postorder(node)
if node.left â‰* null then postorder(node.left)
if node.right â‰* null then postorder(node.right)
print node.value

this took me about 10s to find
--
Nick Keighley

Thanks for your efforts ;-) but u used recursion
****************************************
with recursion, for preorder :
-------------------------
preorder(node){
if(node){
print info(node)
preorder(node->left)
preorder(node->right)
}
with recursion, for postorder :
-------------------------
postorder(node){
if(node){

postorder(node->left)
postorder(node->right)
print(info(node))
with recursion, for postorder :
-------------------------
inorder(node){
if(node){

inorder(node->left)
inorder(info(node))
inorder(node->right)
}
**********************************

i hope it clrifies the intent...
i need the same output without any recursive call
it must be same as i have done above for inorder,
preorder just needs a little modification
for postorder one needs to store some info about left/rigth child
but i am not sure what???

[Martin Ambuhl]

Nick Keighley wrote:

On 19 Apr, 07:40, [e-mail] wrote:

>Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.

from wiki:

postorder(node)
if node.left â‰* null then postorder(node.left)
if node.right â‰* null then postorder(node.right)
print node.value

this took me about 10s to find

And it looks like recursion, forbidden by the given conditions.

[saki]

On Apr 19, 11:40 am, [e-mail] wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.
thnx

looks like this algorithm will work.

for each node there are 2 states.
1)wait state
2)process state

initialise stack to the (root,wait)
while(stack is not empty)
{
pop an element from stack;
if (state=process)
then print the node;
else(i.e state is wait)
{
push the (element,process);
if(node.right!=NULL)push(node->right,wait);
if(node.left!=NULL)push(node->left,wait);
}
}
this algorithm should work.
i have not written all the details but this is the basic algorithm.
if there are any loopholes,please tell me.
thank you.

[nishit.gupta]

On Apr 20, 3:24 am, saki <[e-mail]:

On Apr 19, 11:40 am, [e-mail] wrote:

Can somebody please help me for algorithm for postorder bst traversal
without recursion.
It should use stack. i am not able to implement it.
thnx

looks like this algorithm will work.

for each node there are 2 states.
1)wait state
2)process state

initialise stack to the (root,wait)
while(stack is not empty)
{
pop an element from stack;
if (state=process)
then print the node;
else(i.e state is wait)
{
push the (element,process);
if(node.right!=NULL)push(node->right,wait);
if(node.left!=NULL)push(node->left,wait);
}

}

this algorithm should work.
i have not written all the details but this is the basic algorithm.
if there are any loopholes,please tell me.
thank you.

yessss....algo is correct....basically login is OK