Depth-first traversal using a stack, is a well-known technique for traversing large trees, when the process stack may not be large enough. For reference, here is one simple implementation:
#include <stack>
struct tree {
int value;
tree *left;
tree *right;
};
void preorder (tree *t, void (*visit) (tree *)) {
std::stack<tree *> work;
if (t == nullptr)
return;
work.push (t);
while (! work.empty ()) {
t = work.top ();
work.pop ();
visit (t);
if (t->right)
work.push (t->right);
if (t->left)
work.push (t->left);
}
}
However, this algorithm does a pre-order traversal, i.e. the root of each subtree is visited before its children. But how about a post-order or an in-order traversal? When we pop a node from the stack, we are in two different situations: we may need to visit the node now or we may need to push its children and visit it later.
The insight is to use a secondary stack, in which to keep track of the parent nodes, which have to be visited later. When a node comes out of the stack for the first time, we put it back, together with its children, in the appropriate order, but we also put it on the secondary stack. After we have processed all of the node's children (or all of the left subtree, for an in-order traversal), the node pops off the primary stack again, but this time it's also at the top of the secondary stack! Now we know the time has come to process it.
The following two functions implement this idea for in-order and post-order traversals:
void inorder (tree *t, void (*visit) (tree *)) {
std::stack<tree *> parents;
std::stack<tree *> work;
if (t == nullptr)
return;
work.push (t);
while (! work.empty ()) {
t = work.top ();
work.pop ();
if (! parents.empty () && t == parents.top()) {
parents.pop ();
visit (t);
} else {
parents.push (t);
if (t->right)
work.push (t->right);
work.push (t);
if (t->left)
work.push (t->left);
}
}
}
void postorder (tree *t, void (*visit)(tree *)) {
std::stack<tree *> parents;
std::stack<tree *> work;
if (t == nullptr)
return;
work.push (t);
while (! work.empty ()) {
t = work.top ();
if (! parents.empty () && t == parents.top ()) {
work.pop ();
parents.pop ();
visit (t);
} else {
parents.push (t);
if (t->right)
work.push (t->right);
if (t->left)
work.push (t->left);
}
}
}
