Post order traversal of binary tree without recurs

Question

What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion?

Answer 1

Here is a solution in C++ that does not require any storage for book keeping in the tree.
Instead it uses two stacks. One to help us traverse and another to store the nodes so we can do a post traversal of them.

std::stack<Node*> leftStack;
std::stack<Node*> rightStack;

Node* currentNode = m_root;
while( !leftStack.empty() || currentNode != NULL )
{
    if( currentNode )
    {
        leftStack.push( currentNode );
        currentNode = currentNode->m_left;
    }
    else
    {
        currentNode = leftStack.top();
        leftStack.pop();

        rightStack.push( currentNode );
        currentNode = currentNode->m_right;
    }
}

while( !rightStack.empty() )
{
    currentNode = rightStack.top();
    rightStack.pop();

    std::cout << currentNode->m_value;
    std::cout << "\n";
}

Answer 2

I was looking for a code snippet that performs well and is simple to customise. Threaded trees are not “simple”. Double stack solution requires O(n) memory. LeetCode solution and solution by tcb have extra checks and pushes...

Here is one classic algorithm translated into C that worked for me:

void postorder_traversal(TreeNode *p, void (*visit)(TreeNode *))
{
    TreeNode   *stack[40];      // simple C stack, no overflow check
    TreeNode  **sp = stack;
    TreeNode   *last_visited = NULL;

    for (; p != NULL; p = p->left)
        *sp++ = p;

    while (sp != stack) {
        p = sp[-1];
        if (p->right == NULL || p->right == last_visited) {
            visit(p);
            last_visited = p;
            sp--;
        } else {
            for (p = p->right; p != NULL; p = p->left)
                *sp++ = p;
        }
    }
}

IMHO this algorithm is easier to follow than well performing and readable wikipedia.org / Tree_traversal pseudocode. For glorious details see answers to binary tree exercises in Knuth’s Volume 1.

Answer 3

Here's a sample from wikipedia:

nonRecursivePostorder(rootNode)
  nodeStack.push(rootNode)
  while (! nodeStack.empty())
    currNode = nodeStack.peek()
    if ((currNode.left != null) and (currNode.left.visited == false))
      nodeStack.push(currNode.left)
    else 
      if ((currNode.right != null) and (currNode.right.visited == false))
        nodeStack.push(currNode.right)
      else
        print currNode.value
        currNode.visited := true
        nodeStack.pop()

Answer 4

Here I am pasting different versions in c# (.net) for reference: (for in-order iterative traversal you may refer to: Help me understand Inorder Traversal without using recursion)

1. wiki (http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations) (elegant)
2. Another version of single stack (#1 and #2: basically uses the fact that in post order traversal the right child node is visited before visiting the actual node - so, we simply rely on the check that if stack top's right child is indeed the last post order traversal node thats been visited - i have added comments in below code snippets for details)
3. Using Two stacks version (ref: http://www.geeksforgeeks.org/iterative-postorder-traversal/) (easier: basically post order traversal reverse is nothing but pre order traversal with a simple tweak that right node is visited first, and then left node)
4. Using visitor flag (easy)
5. Unit Tests

~

public string PostOrderIterative_WikiVersion()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode lastPostOrderTraversalNode = null;
                BinaryTreeNode iterativeNode = this._root;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                while ((stack.Count > 0)//stack is not empty
                    || (iterativeNode != null))
                {
                    if (iterativeNode != null)
                    {
                        stack.Push(iterativeNode);
                        iterativeNode = iterativeNode.Left;
                    }
                    else
                    {
                        var stackTop = stack.Peek();
                        if((stackTop.Right != null)
                            && (stackTop.Right != lastPostOrderTraversalNode))
                        {
                            //i.e. last traversal node is not right element, so right sub tree is not
                            //yet, traversed. so we need to start iterating over right tree 
                            //(note left tree is by default traversed by above case)
                            iterativeNode = stackTop.Right;
                        }
                        else
                        {
                            //if either the iterative node is child node (right and left are null)
                            //or, stackTop's right element is nothing but the last traversal node
                            //(i.e; the element can be popped as the right sub tree have been traversed)
                            var top = stack.Pop();
                            Debug.Assert(top == stackTop);
                            nodes.Add(top.Element);
                            lastPostOrderTraversalNode = top;
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

Here is post order traversal with one stack (my version)

public string PostOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode lastPostOrderTraversalNode = null;
                BinaryTreeNode iterativeNode = null;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if ((iterativeNode.Left == null)
                        && (iterativeNode.Right == null))
                    {
                        nodes.Add(iterativeNode.Element);
                        lastPostOrderTraversalNode = iterativeNode;
                        //make sure the stack is not empty as we need to peek at the top
                        //for ex, a tree with just root node doesn't have to enter loop
                        //and also node Peek() will throw invalidoperationexception
                        //if it is performed if the stack is empty
                        //so, it handles both of them.
                        while(stack.Count > 0) 
                        {
                            var stackTop = stack.Peek();
                            bool removeTop = false;
                            if ((stackTop.Right != null) &&
                                //i.e. last post order traversal node is nothing but right node of 
                                //stacktop. so, all the elements in the right subtree have been visted
                                //So, we can pop the top element
                                (stackTop.Right == lastPostOrderTraversalNode))
                            {
                                //in other words, we can pop the top if whole right subtree is
                                //traversed. i.e. last traversal node should be the right node
                                //as the right node will be traverse once all the subtrees of
                                //right node has been traversed
                                removeTop = true;
                            }
                            else if(
                                //right subtree is null
                                (stackTop.Right == null) 
                                && (stackTop.Left != null) 
                                //last traversal node is nothing but the root of left sub tree node
                                && (stackTop.Left == lastPostOrderTraversalNode))
                            {
                                //in other words, we can pop the top of stack if right subtree is null,
                                //and whole left subtree has been traversed
                                removeTop = true;
                            }
                            else
                            {
                                break;
                            }
                            if(removeTop)
                            {
                                var top = stack.Pop();
                                Debug.Assert(stackTop == top);
                                lastPostOrderTraversalNode = top;
                                nodes.Add(top.Element);
                            }
                        }
                    }
                    else 
                    {
                        stack.Push(iterativeNode);
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        if(iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

Using two stacks

public string PostOrderIterative_TwoStacksVersion()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
                Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
                rightLeftPreOrderStack.Push(this._root);
                while(rightLeftPreOrderStack.Count > 0)
                {
                    var top = rightLeftPreOrderStack.Pop();
                    postOrderStack.Push(top);
                    if(top.Left != null)
                    {
                        rightLeftPreOrderStack.Push(top.Left);
                    }
                    if(top.Right != null)
                    {
                        rightLeftPreOrderStack.Push(top.Right);
                    }
                }
                while(postOrderStack.Count > 0)
                {
                    var top = postOrderStack.Pop();
                    nodes.Add(top.Element);
                }
            }
            return this.ListToString(nodes);
        }

With visited flag in C# (.net):

public string PostOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode iterativeNode = null;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if(iterativeNode.visted)
                    {
                        //reset the flag, for further traversals
                        iterativeNode.visted = false;
                        nodes.Add(iterativeNode.Element);
                    }
                    else
                    {
                        iterativeNode.visted = true;
                        stack.Push(iterativeNode);
                        if(iterativeNode.Right != null)
                        {
                            stack.Push(iterativeNode.Right);
                        }
                        if(iterativeNode.Left != null)
                        {
                            stack.Push(iterativeNode.Left);
                        }
                    }
                }
            }
            return this.ListToString(nodes);
        }

The definitions:

class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;
        public bool visted;
    }

string ListToString(List<int> list)
        {
            string s = string.Join(", ", list);
            return s;
        }

Unit Tests

[TestMethod]
        public void PostOrderTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                string s1 = bst.PostOrderRecursive();
                string s2 = bst.PostOrderIterativeWithVistedFlag();
                string s3 = bst.PostOrderIterative();
                string s4 = bst.PostOrderIterative_WikiVersion();
                string s5 = bst.PostOrderIterative_TwoStacksVersion();
                Assert.AreEqual(s1, s2);
                Assert.AreEqual(s2, s3);
                Assert.AreEqual(s3, s4);
                Assert.AreEqual(s4, s5);
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
                s1 = bst.PostOrderRecursive();
                s2 = bst.PostOrderIterativeWithVistedFlag();
                s3 = bst.PostOrderIterative();
                s4 = bst.PostOrderIterative_WikiVersion();
                s5 = bst.PostOrderIterative_TwoStacksVersion();
                Assert.AreEqual(s1, s2);
                Assert.AreEqual(s2, s3);
                Assert.AreEqual(s3, s4);
                Assert.AreEqual(s4, s5);
            }
            Debug.WriteLine(string.Format("PostOrderIterative: {0}", bst.PostOrderIterative()));
            Debug.WriteLine(string.Format("PostOrderIterative_WikiVersion: {0}", bst.PostOrderIterative_WikiVersion()));
            Debug.WriteLine(string.Format("PostOrderIterative_TwoStacksVersion: {0}", bst.PostOrderIterative_TwoStacksVersion()));
            Debug.WriteLine(string.Format("PostOrderIterativeWithVistedFlag: {0}", bst.PostOrderIterativeWithVistedFlag()));
            Debug.WriteLine(string.Format("PostOrderRecursive: {0}", bst.PostOrderRecursive()));
        }

Answer 5

Python with 1 stack and no flag:

def postorderTraversal(self, root):
    ret = []
    if not root:
        return ret
    stack = [root]
    current = None
    while stack:
        previous = current
        current = stack.pop()
        if previous and ((previous is current) or (previous is current.left) or (previous is current.right)):
            ret.append(current.val)
        else:
            stack.append(current)
            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)

    return ret

And what is better is with similar statements, in order traversal works too

def inorderTraversal(self, root):
    ret = []
    if not root:
        return ret
    stack = [root]
    current = None
    while stack:
        previous = current
        current = stack.pop()
        if None == previous or previous.left is current or previous.right is current:
            if current.right:
                stack.append(current.right)
            stack.append(current)
            if current.left:
                stack.append(current.left)
        else:
            ret.append(current.val)

    return ret

Answer 6

Please see this full Java implementation. Just copy the code and paste in your compiler. It will work fine.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node
{
    Node left;
    String data;
    Node right;

    Node(Node left, String data, Node right)
    {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    public String getData()
    {
        return data;
    }
}

class Tree
{
    Node node;

    //insert
    public void insert(String data)
    {
        if(node == null)
            node = new Node(null,data,null);
        else
        {
            Queue<Node> q = new LinkedList<Node>();
            q.add(node);

            while(q.peek() != null)
            {
                Node temp = q.remove();
                if(temp.left == null)
                {
                    temp.left = new Node(null,data,null);
                    break;
                }
                else
                {
                    q.add(temp.left);
                }

                if(temp.right == null)
                {
                    temp.right = new Node(null,data,null);
                    break;
                }
                else
                {
                    q.add(temp.right);
                }
            }
        }
    }

    public void postorder(Node node)
    {
        if(node == null)
            return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.getData()+" --> ");
    }

    public void iterative(Node node)
    {
        Stack<Node> s = new Stack<Node>();
        while(true)
        {
            while(node != null)
            {
                s.push(node);
                node = node.left;
            }



            if(s.peek().right == null)
            {
                node = s.pop();
                System.out.print(node.getData()+" --> ");
                if(node == s.peek().right)
                {
                    System.out.print(s.peek().getData()+" --> ");
                    s.pop();
                }
            }

            if(s.isEmpty())
                break;

            if(s.peek() != null)
            {
                node = s.peek().right;
            }
            else
            {
                node = null;
            }
        }
    }
}

class Main
{
    public static void main(String[] args) 
    {
        Tree t = new Tree();
        t.insert("A");
        t.insert("B");
        t.insert("C");
        t.insert("D");
        t.insert("E");

        t.postorder(t.node);
        System.out.println();

        t.iterative(t.node);
        System.out.println();
    }
}