Understanding the logic in iterative Postorder traversal implementation on a Binary tree

Question

I was trying to understand how it is so intuitive to implement postorder traversal using 2 stacks. How did someone come up with it, is it just an observation or some particular way of thinking which helps one come up with such methods. If yes then please explain how to think in the right direction.

Answer 1

Let me explain how I stumbled on the solution:

You start off with this simple observation: prima facie, the pre-order and post-order traversal differ only in their order of operations:

preOrder(node):
    if(node == null){
         return
    }
    visit(node)
    preOrder(node.leftChild)
    preOrder(node.rightChild)

postOrder(node):
    if(node == null){
         return
    }
    postOrder(node.leftChild)
    postOrder(node.rightChild)
    visit node

The preOrder function does some computations (visiting the node) and two recursive calls to itself - lets call this order 'VLR'. The postOrder function makes two recursive calls and then does visits the node ('LRV').

The preOrder lends itself to a simple iterative implementation, where we visit the node, and push the computation corresponding to the recursive calls onto a stack.

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();
        visit(currentNode);
        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }
    }

The stack contains the list of unvisited nodes. We pop a node, visit it, push its right child, push the left child. Repeat. This gives us preOrder.

(Note: For VLR, we push the right child before the left child because a stack is LIFO - we visit the child pushed last before we visit the child pushed before it - and we want to visit the left child before the right child. For VRL, we would have to revser the order)

Say we do this we push the right child, push the left child, and only then visit the node (kind of mirroring the relative order of (1) recursive calls and (2) node visit in postOrder. We try to make VLR to LRV by moving V at the end).

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();
        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }
        visit(currentNode);
    }   

This should give us postOrder, right? No. This is still preOrder. What defines preOrder is NOT that we visited a node before pushing children on the stack, but that we popped (and hence visited) the children on the stack AFTER permanently removing the node (and hence after visiting it) from the stack. The children in the stack are eventually, at some point, popped and visited, but their parent has already been popped and visited - and hence this is preOrder. This approach seems like a dead-end.

But there is another way! Instead of turning VLR into LRV by moving V fro the front to end, we can make 'VLR' into 'LRV' by reversing the order of L and R in VLR (making it VRL), and then reversing the resulting 'VRL' to make it 'LRV'.

The sequence generated by left-to-right postOrder traversal (LRV) is the same as the reverse of 'VRL' - the sequence generated by right-to-left preOrder traversal.

Let's tweak our iterative preOrder by making it VRL:

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }

        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        visit(currentNode);
    }   

This will give us a VRL preOrder (a sequence whose reverse is LRV, the postOrder). We just need to traverse it in reverse! This is where the need for a second stack comes in. If we push every node we visit to another stack, and then just traverse it top to down, we will get our postOrder!

Here is my final solution:

    var reverseStack = new Stack();
        while(!nodeStack.isEmpty()){
            var currentNode = nodeStack.pop()
            reverseStack.push(currentNode)
            if (currentNode.leftChild){
                nodeStack.push(currentNode.leftChild)
            }

            if (currentNode.rightChild){
                nodeStack.push(currentNode.rightChild)
            }
        }

        while(!reverseStack.isEmpty()){
            console.log(reverseStack.pop().getElement())
        }

There are minor optimizations you can make - which will give you the standard two stack solution you see online. Please note that two stacks are not necessary - and it is possible to implement postOrder with just one stack - for example, if we keep track of the last node visited.