why 2 stacks are so effective for post-order transverses

Question

So I am familiar with postorder traversing:

L -> R -> P (Left to Right to Parent).

I saw a code that could perform a postorder traversal quite elegantly using 2 stacks:

public void postOrderTransverse(Node r){
    if(r == null){return;}
    Stack<Node> s = new Stack<Node>();
    Stack<Node> reverser = new Stack<Node>();
    s.push(r);
    while(!s.isEmpty()){
        Node temp = s.pop();
        reverser.push(temp);
        if (temp.left != null){
            s.push(temp.left);}
        if(temp.right != null){
            s.push(temp.right);}
    }
    while(!reverser.empty()){
        System.out.print(reverser.peek());
        reverser.pop();
    }
}

(via http://articles.leetcode.com/binary-tree-post-order-traversal/)

where essentially, one Stack just reverses the other. I am just very curious about how this works. I have a hypothesis that Stack s accepts input so that the output would be something like P -> R -> L, and it just passes that onto Stack reverser which spits out L -> R .-> P since it's Last In First Out.

However, just trying to think through the processes of this algorithm, I'm struggling to understand how and why Stack s takes its input the way it does. Hoping I could get some insight on here! Thanks :)

It is doing a pre-order traversal using the first stack, and pushing the results onto the second stack, then popping that stack, which gives you a post-order traversal just by reversing the results. — user207421, Aug 19 '16 at 05:01
@EJP, it is not doing pre-order traversal, as it traverses right node first. In fact this is a loop version of a recursive post-order traversal. — user3707125, Aug 19 '16 at 05:15

score 2 · Accepted Answer · edited May 23 '17 at 11:51

The code you provided is simply a loop version of the corresponding recursive solution:

public void postOrderTraverseRecursive(Node r){
    if(r == null){return;}

    if (r.left != null){
        postOrderTraverseRecursive(r.left);}
    if(r.right != null){
        postOrderTraverseRecursive(r.right);}

    System.out.print(r);
}

In order to transform recursion to a loop we need to reverse the order of the statements execution. We will use one stack to maintain recursion invocations, and one to maintain output of the recursion (i.e. System.out.print statement arguments).

Your code with more meaningful variable names and explanation:

public void postOrderTraverse(Node root){
    if(root == null){return;}
    Stack<Node> recursionStack = new Stack<Node>();
    Stack<Node> printStack = new Stack<Node>();
    recursionStack.push(root);
    while(!recursionStack.isEmpty()){
        Node node = recursionStack.pop();
        /* Recursion iteration start */
        // According to the recursion we should process left->right->node.
        // Considering that in the loop version we have to reverse the order of invocations,
        // we are processing node->right->left
        printStack.push(node); // node is added to printStack immediately
        // left is added to recursionStack first, but because
        // of the FILO nature of the stack it will be processed last
        if (node.left != null){
            recursionStack.push(node.left);}
        // right is added to recursionStack last, but because
        // of the FILO nature of the stack it will be processed first
        if(node.right != null){
            recursionStack.push(node.right);}
        /* Recursion iteration end */
    }
    // We've processed all the input and now we have reversed
    // history of the prints, processing them in reverse order
    // to receive the actual one
    while(!printStack.empty()){
        System.out.print(printStack.peek());
        printStack.pop();
    }
}

why 2 stacks are so effective for post-order transverses

1 Answers1