Iterative post order traversal without keeping visited flag

Question

Why is it necessary to keep visited flag for iterative post order traversal and not for inorder or pre order iterative traversal.

Is it possible to do post order traversal without keeping visited flag ?

Answer 1

Here's a post-order visit:

postordervisit(t)
{   if not(leaf(t))
    { postordervisit(left(t);
      postordervisit(right(t));
    }
L1: process(t);
        L2:
}

It doesn't use any flags. Why do you think a flag is necessary?

Maybe I don't understand the phrase, "iterative post order traversal". By symmetry, if you think that "iterative preorder traversal" doesn't need a flag, I contend you'd have to believe "iterative postorder traversal" is also flag free, and vice-versa.

EDIT: My bad, must be late at night. "Iterative" meaning "implement without recursion". OK, so you implement your own stack of nodes, and you have to implement what amounts to a stack of return addresses. I think the flag is simulating the effect of the return address knowing whether to go to L1 or L2 next. And since you need this for post order, by symmetry you need it for pre-order.

EDIT October 2010: My bad again, the algorithm provided wasn't post-order. Revised.