Questions regarding Iterative Traversal Algorithm?

Tag: algorithm Author: shanpao098765 Date: 2009-08-12

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 ?

Are pointers or references to parent nodes available, or do you need to use an explicit stack?

Best Answer

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.

comments:

I presume by iterative he means that you implement postordervisit without any recursive calls.
Yes that is right.
this is probably a homework question.
I suspect I answered it a way that still leaves it as a homework question :-}
Either the Wikipedia (en.wikipedia.org/wiki/Postorder_traversal#Depth-first_Traversal) lies, or your traversal is not post order.

Other Answer1

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.leetcode.com/2010/10/binary-tree-post-order-traversal.html

Other Answer2

I found a problem in the solution of user 1337c0d3r: it is simply a pre-order in reverse order. My solution uses an "active list" to mark the nodes in the stack.

(You could store the mark flag in the stack. Will post that solution separately. )

void print_postorder(Nodes const& roots)
{
    typedef std::set<Node const*> ActiveList;
    ActiveList activeNodes;
    vector<Nodes::const_iterator> stack(1, roots.begin());

    while( stack.empty() == false )
    {
        Nodes::const_iterator node = stack.back();
        ActiveList::iterator activeEntry = activeNodes.find( &*node );

        if( activeEntry == activeNodes.end() )
        {
            // This node is now active.
            activeNodes.insert( &*node );
            // Plan to visit each child.
            for( Nodes::const_reverse_iterator rchild = node->children.rbegin();
                 rchild != node->children.rend(); ++rchild )
            {
                Nodes::const_reverse_iterator rchild2 = rchild;
                Nodes::const_iterator child = (++rchild2).base();
                stack.push_back(child);
            }
        }
        else
        {
            // Post-order visit the node.
            std::size_t depth = activeNodes.size();
            for( std::size_t i = 0; i < 4 * depth; ++i )
                cout << ' ';  // Indent
            cout << node->name << endl;
            // We're finished with this node.
            activeNodes.erase( activeEntry );
            stack.pop_back();
        }
    }
}

// Try this for yourself!  Tree representation:

#include <vector>
#include <set>

struct Node;
typedef std::vector<Node> Nodes;
struct Node
{
    std::string name;
    Nodes children;
};

Other Answer3

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.