Non-recursive post order traversal

Question

Hi,

I saw the following post order traversal algorithm in some website... it seems to be correct. I just want to verify that this algorithm works correctly — is this algorithm correct for post order traversal without recursion?

void postOrderTraversal(Tree *root)
{
    node * previous = null;
    node * s = null;
    push(root);
    while( stack is not empty )
    {
        s = pop();

        if(s->right == null and s->left == null)
        {
            previous = s;
            process s;
        }
        else
        {
            if(s->right == previous or s->left == previous)
            {
                previous = s;
                process s;
            }
            else
            {
                push( s );
                if(s->right) { push(s->right); }
                if(s->left)  { push(s->left);  }
            }
        }
    }
}

Answer 1

Barry and Cirno, the posted algorithm is a non-recursive one as the guy says. I don't understand what you guys are talking about.

Answer 2

no here prev should not start with null eg:for bst having nodes 5 2 1 3 7 6 8 0 it will not consider zero because at 1 its right is null and this time previous will also be null hence it will not consider its left child i.e. 0 write previous=any value but not null