algorithmtree-traversal

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


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 descent 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.


Solution

  • 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.