Questions regarding Iterative Traversal Algorithm ?

Question

Hi All,

Why is it necessary to keep visited flag for iterative post order traversal and not for inorder or pre order iterative traversal and 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.

Answer 2

I believe the algorithm show in previous posting for port-order traversal is in as it "processes" the node before visiting the left sub-tree. Postorder Traversal is essentially the same as Reverse Polish Notation in which the operands (leaf nodes or sub-trees) precede the operator (the next higher sub-tree node).

A corrected postorder traversal algorith would be:

postordervisit(t) { if null(t) return;
postordervisit(right(t)); postordervisit(left(t); process(t); }

This would visit the leaf or sub-tree nodes before visiting the root of the sub-tree.

Answer 3

Postorder traversal iterative version could be implemented without using visited flags, it is just more difficult to implement.

See here for two solutions for iterative postorder traversal without using any visited flags.

http://www.ihas1337code.com/2010/10/binary-tree-post-order-traversal.html