Post-order Tree Walk without marking node?

Question

I saw a question which is asking designing algorithm for "Post-order Tree Walk without marking node".

What does this question mean?

Answer 1

There are generally 3 ways to visit nodes in a tree: pre-order, in-order, post-order.

Pre-order means you process the node before processing the children.

In-order means you process the the left children (assuming here that it is a binary tree), then the current node, then the right children.

Post-order means you process a node after processing both children.

"Processing a node" could by any operation on a node, as simple as writing the stored payload of the node to the console.

Doing it without marking means not using an indicator (usually an extra field in the node) to show that a node has been visited. As Peter G. mentioned, the indicator should not be needed with recursive implemenations.

Answer 2

The standard recursive tree traversal algorithms need no marking of nodes. Marking or modification of nodes is only needed for constant space traversal algorithms.