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

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.

I realize this post is several years old, but none of the answers seem to directly answer the question, so I figured I'd write up something somewhat simple.

This assumes an integer indexed graph; but you can certainly adapt it as necessary. The key to doing DFS iteratively and still having pre-order/post-order operations is to NOT just append every child at once, but instead, behave exactly as recursive DFS would, which is adding just one child-node to the stack at a time, and only removing them from the stack once it has finished. I accomplish this in my example by creating a wrapper node with the adjacency list as a stack. Just omit the cycle check if you wish to allow cycles (it doesn't traverse visited nodes anyway, so it will still work)

class Stack(object):
    def __init__(self, l=None):
        if l is None:
            self._l = []
        else:
            self._l = l
        return

    def pop(self):
        return self._l.pop()

    def peek(self):
        return self._l[-1]

    def push(self, value):
        self._l.append(value)
        return

    def __len__(self):
        return len(self._l)

class NodeWrapper(object):
    def __init__(self, graph, v):
        self.v = v
        self.children = Stack(graph[v])
        return

def iterative_postorder(G, s):
    onstack = [False] * len(G)
    edgeto = [None] * len(G)
    visited = [False] * len(G)

    st = Stack()
    st.push(NodeWrapper(G, s))

    while len(st) > 0:
        vnode = st.peek()
        v = vnode.v
        if not onstack[v]:
            print "Starting %d" % (v)
        visited[v] = True
        onstack[v] = True
        if len(vnode.children) > 0:
            e = vnode.children.pop()
            if onstack[e]:
                cycle = [e]
                e = v
                while e != cycle[0]:
                    cycle.append(e)
                    e = edgeto[e]
                raise StandardError("cycle detected: %s, graph not acyclic" % (cycle))
            if not visited[e]:
                edgeto[e] = v
                st.push(NodeWrapper(G, e))
        else:
            vnode = st.pop()
            onstack[vnode.v] = False
            print 'Completed %d' % (vnode.v)