Iterative post order traversal without keeping visited flag
https://stackoverflow.com/questions/1350311
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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 ?
Solution
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.
OTHER TIPS
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
If we start with the simple recursive postorder algorithm,
def postorder1(node, f):
# a:
if node is None:
return None
postorder1(node.left, f)
# b:
postorder1(node.right, f)
# c:
f(node)
we can chop the function into three parts "a", "b", and "c", and then naively translate it into an iterative algorithm by emulating a virtual call stack:
def postorder2(node, f):
stack = [("a", node)]
while stack:
go, node = stack.pop()
if go == "a":
if node is not None:
stack.append(("b", node))
stack.append(("a", node.left))
elif go == "b":
stack.append(("c", node))
stack.append(("a", node.right))
elif go == "c":
f(node)
From this we observe that the stack can only be modified in one of three ways:
[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]
This implies that:
- "a" can only appear at most once at the top of the stack, whereas
- "b" and "c" and appear any number of times in the middle of the stack, possibly interleaved.
Therefore, we don't really need to store "a" inside the stack – a single variable to store "a" would be enough. This allows us to simplify the naive iterative algorithm into the more conventional form:
def postorder3(node, f):
stack = []
while True:
if node:
stack.append((True, node))
node = node.left
elif stack:
left, top = stack.pop()
if left:
stack.append((False, top))
node = top.right
else:
f(top)
else:
break
The boolean flag on the stack is the “visited flag”. In this example, we don’t store the flag directly on the nodes, but within our stack, but the net effect is the same. Some variants of the algorithm use a “last visited node” variable instead, but that requires a way to compare nodes for “identity” (pointer/reference equality), which we do not assume here.
This flag is an essential part of the algorithm because, as noted in our analysis earlier, the "b" and "c" entries on the stack can appear in completely arbitrary ways. We need some kind of information to tell us whether we should traverse rightward or call f.
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;
};
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.
Flags are not necessary and should be avoided since a reader should not modify anything, and any modification would not allow concurrency, for example. Here is an implementation of an iterative post-order traversal in C as a macro. It works for any tree type with proper configuration, and can do also the reversed post-order. The whole library, which also implements an iterative pre-order traversal, is here.
#define W_TREE_FOR_EACH_POSTORDER(T,Child,self) \
W_DECLARE(W_CAT(Child,po1), T *Child) \
W_DECLARE(W_CAT(Child,po2), T* W_ID(node) = (self)) \
W_DECLARE(W_CAT(Child,po3), T** W_ID(stack) = NULL ) \
W_DECLARE(W_CAT(Child,po9), int W_ID(_finish_) = 0 ) \
if (W_ID(node) == NULL) \
; \
else \
W_BEFORE(W_CAT(Child,po4), goto W_LABEL(6,Child); ) \
while (!W_ID(_finish_)) \
W_BEFORE (W_CAT(Child,po5), \
W_LABEL(6,Child): \
while (W_ID(node)) { \
BOOST_PP_IF(W_REVERSED, \
W_TREE_FOR_EACH_IMMEDIATE_REVERSED(T,W_CAT(Child,_child), W_ID(node)) \
if (W_CAT(Child,_child,_ix) < W_TREE_GET_DEGREE(W_ID(node))-1) \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_CAT(Child,_child) ); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_RIGHTMOST(W_ID(node)); \
, /* else */ \
W_TREE_FOR_EACH_IMMEDIATE(T,W_CAT(Child,_child), W_ID(node)) \
if (W_CAT(Child,_child,_ix) > 0) \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_CAT(Child,_child) ); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_LEFTMOST(W_ID(node)); \
) \
} \
W_ID(node) = W_DYNAMIC_STACK_POP( W_ID(stack) ); \
BOOST_PP_IF(W_REVERSED, \
if (W_ID(node) && W_TREE_NEXT_LEFTMOST(W_ID(node)) \
&& W_DYNAMIC_STACK_PEEK_SAFE(W_ID(stack),NULL) == W_TREE_NEXT_LEFTMOST(W_ID(node)) ) { \
W_DYNAMIC_STACK_POP(W_ID(stack)); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_LEFTMOST(W_ID(node)); \
goto W_LABEL(6,Child); \
} \
, /* else */ \
if (W_ID(node) && W_TREE_NEXT_RIGHTMOST(W_ID(node)) \
&& W_DYNAMIC_STACK_PEEK_SAFE(W_ID(stack),NULL) == W_TREE_NEXT_RIGHTMOST(W_ID(node)) ) { \
W_DYNAMIC_STACK_POP(W_ID(stack)); \
W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) ); \
W_ID(node) = W_TREE_NEXT_RIGHTMOST(W_ID(node)); \
goto W_LABEL(6,Child); \
} \
) \
Child = W_ID(node); \
W_ID(node) = NULL; \
) \
W_AFTER(W_CAT(Child,po8), \
W_ID(_finish_) = W_DYNAMIC_STACK_IS_EMPTY(W_ID(stack)); \
if (W_ID(_finish_)) \
W_DYNAMIC_STACK_FREE(W_ID(stack)); \
) \
/**/
It can be used like this. To get reversed post-order, redefine W_REVERSED to 1. To change the next field fetch operation, redefine W_TREE_NEXT(tree,ix) and for variadic degree trees, redefine W_TREE_GET_DEGREE(tree).
#include <wondermacros/tree/for_each.h>
struct bintree {
struct bintree* next[2];
const char* value;
};
struct bintree* root = ...
W_TREE_FOR_EACH_POSTORDER(struct bintree, node, root) {
printf("%s\n", node->value);
}
