Iterative depth-first tree traversal with pre- and post-visit at each node

Question

Can anyone point me at pseudocode for iterative depth-first tree traversal, where it's possible to do actions on each node at both pre- and post- order?

That is, an action before decent into a node's children, then an action after ascent from the children?

Also, my tree is not binary - each node has 0..n children.

Basically, my case is transforming a recursive traversal, where I do the pre- and post- operations on the current node, either side of the recursion into the children.

Answer 1

My plan is to use two stacks. One for pre-order traversal and another one is for post-order traversal. Now, I run standard iterative DFS (depth-first traversal), and as soon as I pop from the "pre" stack i push it in "post" stack. At the end, my "post" stack will have child node at top and and root at bottom.

treeSearch(Tree root) {
    Stack pre;
    Stack post;
    pre.add(root);
    while (pre.isNotEmpty()) {
        int x = pre.pop();
        // do pre-order visit here on x
        post.add(x);
        pre.addAll(getChildren(x));
    }
    while (post.isNotEmpty()) {
        int y = post.pop();
        // do post-order visit here on y
    }
}

root will always be traversed last from post stack as it will stay at the bottom.

This is simple java code:

public void treeSearch(Tree tree) {
    Stack<Integer> preStack = new Stack<Integer>();
    Stack<Integer> postStack = new Stack<Integer>();
    preStack.add(tree.root);
    while (!preStack.isEmpty()) {
        int currentNode = preStack.pop();
        // do pre-order visit on current node
        postStack.add(currentNode);
        int[] children = tree.getNeighbours(currentNode);
        for (int child : children) {
            preStack.add(child);
        }
    }

    while (!postStack.isEmpty()) {
        int currentNode = postStack.pop();
        // do post-order visit on current node
    }
}

I am assuming this is a tree, so: no cycle and no revisiting the same node again. But, if we want we can always have a visited array and check against that.