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]

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?

 

[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???

 

[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???

ohh sorry for top post!!

 

[Nick Keighley]

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

 

[saki]

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

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

 

[nishit.gupta]

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

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]

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]

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]

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