Post order traversal of binary tree without recursion

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

Here's the version with one stack and without a visited flag:

private void postorder(Node head) {
  if (head == null) {
    return;
  }
  LinkedList<Node> stack = new LinkedList<Node>();
  stack.push(head);

  while (!stack.isEmpty()) {
    Node next = stack.peek();

    boolean finishedSubtrees = (next.right == head || next.left == head);
    boolean isLeaf = (next.left == null && next.right == null);
    if (finishedSubtrees || isLeaf) {
      stack.pop();
      System.out.println(next.value);
      head = next;
    }
    else {
      if (next.right != null) {
        stack.push(next.right);
      }
      if (next.left != null) {
        stack.push(next.left);
      }
    }
  }
}

Here's a link which provides two other solutions without using any visited flags.

https://leetcode.com/problems/binary-tree-postorder-traversal/

This is obviously a stack-based solution due to the lack of parent pointer in the tree. (We wouldn't need a stack if there's parent pointer).

We would push the root node to the stack first. While the stack is not empty, we keep pushing the left child of the node from top of stack. If the left child does not exist, we push its right child. If it's a leaf node, we process the node and pop it off the stack.

We also use a variable to keep track of a previously-traversed node. The purpose is to determine if the traversal is descending/ascending the tree, and we can also know if it ascend from the left/right.

If we ascend the tree from the left, we wouldn't want to push its left child again to the stack and should continue ascend down the tree if its right child exists. If we ascend the tree from the right, we should process it and pop it off the stack.

We would process the node and pop it off the stack in these 3 cases:

1. The node is a leaf node (no children)
2. We just traverse up the tree from the left and no right child exist.
3. We just traverse up the tree from the right.

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()

This is the approach I use for iterative, post-order traversal. I like this approach because:

1. It only handles a single transition per loop-cycle, so it's easy to follow.
2. A similar solution works for in-order and pre-order traversals

Code:

enum State {LEFT, RIGHT, UP, CURR}

public void iterativePostOrder(Node root) {
  Deque<Node> parents = new ArrayDeque<>();
  Node   curr = root;
  State state = State.LEFT;

  while(!(curr == root && state == State.UP)) {
    switch(state) {
      case LEFT:
        if(curr.left != null) {
          parents.push(curr);
          curr = curr.left;
        } else {
          state = RIGHT;
        }
        break;
      case RIGHT:
        if(curr.right != null) {
          parents.push(curr);
          curr = curr.right;
          state = LEFT;
        } else {
          state = CURR;
        }
        break; 
      case CURR:
        System.out.println(curr);
        state = UP;
        break;
      case UP: 
        Node child = curr;
        curr = parents.pop();
        state = child == curr.left ? RIGHT : CURR;
        break;
      default:
        throw new IllegalStateException();
    }
  }
}

Explanation:

You can think about the steps like this:

1. Try LEFT

• if left-node exists: Try LEFT again
• if left-node does not exist: Try RIGHT

2. Try RIGHT

• If a right node exists: Try LEFT from there
• If no right exists, you're at a leaf: Try CURR

3. Try CURR

• Print current node
• All nodes below have been executed (post-order): Try UP

4. Try UP

• If node is root, there is no UP, so EXIT
• If coming up from left, Try RIGHT
• If coming up from right, Try CURR

import java.util.Stack;

public class IterativePostOrderTraversal extends BinaryTree {

	public static void iterativePostOrderTraversal(Node root){
		Node cur = root;
		Node pre = root;
		Stack<Node> s = new Stack<Node>();
		if(root!=null)
			s.push(root);
		System.out.println("sysout"+s.isEmpty());
		while(!s.isEmpty()){
			cur = s.peek();
			if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
				if(cur.left!=null){
					s.push(cur.left);
				}
				else if(cur.right!=null){
					s.push(cur.right);
				}
				if(cur.left==null && cur.right==null){
					System.out.println(s.pop().data);
				}
			}else if(pre==cur.left){// we are traversing up the tree from the left
				if(cur.right!=null){
					s.push(cur.right);
				}else if(cur.right==null){
					System.out.println(s.pop().data);
				}
			}else if(pre==cur.right){// we are traversing up the tree from the right
				System.out.println(s.pop().data);
			}
			pre=cur;
		}
	}
	
	public static void main(String args[]){
		BinaryTree bt = new BinaryTree();
		Node root = bt.generateTree();
		iterativePostOrderTraversal(root);
	}
	
	
}

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";
}

// the java version with flag

public static <T> void printWithFlag(TreeNode<T> root){
	if(null == root) return;
	
	Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
	stack.add(root);
	
	while(stack.size() > 0){
		if(stack.peek().isVisit()){
			System.out.print(stack.pop().getValue() + "  ");
		}else{
			
			TreeNode<T> tempNode = stack.peek();
			if(tempNode.getRight()!=null){
				stack.add(tempNode.getRight());
			}
			
			if(tempNode.getLeft() != null){
				stack.add(tempNode.getLeft());
			}
			
			
			
			tempNode.setVisit(true);
			
			
		}
	}
}

Depth first, post order, non recursive, without stack

When you have parent:

   node_t
   {
     left,
     right
     parent
   }

   traverse(node_t rootNode)
   {
     bool backthreading = false	
     node_t node = rootNode
   	 
     while(node <> 0)
	
   		if (node->left <> 0) and backthreading = false then
			   node = node->left
		
   			continue 
		endif
	
         >>> process node here <<<

	
		if node->right <> 0 then
			lNode = node->right
			backthreading = false
		else
			node = node->parent
		
			backthreading = true
		endif
	endwhile

The logic of Post order traversal without using Recursion

In Postorder traversal, the processing order is left-right-current. So we need to visit the left section first before visiting other parts. We will try to traverse down to the tree as left as possible for each node of the tree. For each current node, if the right child is present then push it into the stack before pushing the current node while root is not NULL/None. Now pop a node from the stack and check whether the right child of that node exists or not. If it exists, then check whether it's same as the top element or not. If they are same then it indicates that we are not done with right part yet, so before processing the current node we have to process the right part and for that pop the top element(right child) and push the current node back into the stack. At each time our head is the popped element. If the current element is not the same as the top and head is not NULL then we are done with both the left and right section so now we can process the current node. We have to repeat the previous steps until the stack is empty.

def Postorder_iterative(head):
    if head is None:
        return None
    sta=stack()
    while True:
        while head is not None:
            if head.r:
                sta.push(head.r)
            sta.push(head)
            head=head.l
        if sta.top is -1:
            break
        head = sta.pop()
        if head.r is not None and sta.top is not -1  and head.r is sta.A[sta.top]:
            x=sta.pop()
            sta.push(head)
            head=x
        else:
            print(head.val,end = ' ')
            head=None
    print()    

void postorder_stack(Node * root){
    stack ms;
    ms.top = -1;
    if(root == NULL) return ;

    Node * temp ;
    push(&ms,root);
    Node * prev = NULL;
    while(!is_empty(ms)){
        temp = peek(ms);
        /* case 1. We are nmoving down the tree. */
        if(prev == NULL || prev->left == temp || prev->right == temp){
             if(temp->left)
                  push(&ms,temp->left);
             else if(temp->right)
                  push(&ms,temp->right);
             else {
                /* If node is leaf node */
                   printf("%d ", temp->value);
                   pop(&ms);
             }
         }
         /* case 2. We are moving up the tree from left child */
         if(temp->left == prev){
              if(temp->right)
                   push(&ms,temp->right);
              else
                   printf("%d ", temp->value);
         }

        /* case 3. We are moving up the tree from right child */
         if(temp->right == prev){
              printf("%d ", temp->value);
              pop(&ms);
         }
         prev = temp;
      }

}

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();
	}
}

Here I am pasting different versions in c# (.net) for reference: (for in-order iterative traversal you may refer to: https://stackoverflow.com/questions/2116662/help-me-understand-inorder-traversal-without-using-recursion/24719707#24719707)

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()));
        }

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

I have not added the node class as its not particularly relevant or any test cases, leaving those as an excercise for the reader etc.

void postOrderTraversal(node* root)
{
	if(root == NULL)
		return;

	stack<node*> st;
	st.push(root);

	//store most recent 'visited' node
	node* prev=root;

	while(st.size() > 0)
	{
		node* top = st.top();
		if((top->left == NULL && top->right == NULL))
		{
			prev = top;
			cerr<<top->val<<" ";
			st.pop();
			continue;
		}
		else
		{
			//we can check if we are going back up the tree if the current
			//node has a left or right child that was previously outputted
			if((top->left == prev) || (top->right== prev))
			{
				prev = top;
				cerr<<top->val<<" ";
				st.pop();
				continue;
			}

			if(top->right != NULL)
				st.push(top->right);

			if(top->left != NULL)
				st.push(top->left);
		}
	}
	cerr<<endl;
}

running time O(n) - all nodes need to be visited AND space O(n) - for the stack, worst case tree is a single line linked list

It's very nice to see so many spirited approaches to this problem. Quite inspiring indeed!

I came across this topic searching for a simple iterative solution for deleting all nodes in my binary tree implementation. I tried some of them, and I tried something similar found elsewhere on the Net, but none of them were really to my liking.

The thing is, I am developing a database indexing module for a very specific purpose (Bitcoin Blockchain indexing), and my data is stored on disk, not in RAM. I swap in pages as needed, doing my own memory management. It's slower, but fast enough for the purpose, and with having storage on disk instead of RAM, I have no religious bearings against wasting space (hard disks are cheap).

For that reason my nodes in my binary tree have parent pointers. That's (all) the extra space I'm talking about. I need the parents because I need to iterate both ascending and descending through the tree for various purposes.

Having that in my mind, I quickly wrote down a little piece of pseudo-code on how it could be done, that is, a post-order traversal deleting nodes on the fly. It's implemented and tested, and became a part of my solution. And it's pretty fast too.

The thing is: It gets really, REALLY, simple when nodes have parent pointers, and furthermore since I can null out the parent's link to the "just departed" node.

Here's the pseudo-code for iterative post-order deletion:

Node current = root;
while (current)
{
  if (current.left)       current = current.left;  // Dive down left
  else if (current.right) current = current.right; // Dive down right
  else
  {
    // Node "current" is a leaf, i.e. no left or right child
    Node parent = current.parent; // assuming root.parent == null
    if (parent)
    {
      // Null out the parent's link to the just departing node
      if (parent.left == current) parent.left = null;
      else                        parent.right = null;
    }
    delete current;
    current = parent;
  }
}
root = null;

If you are interested in a more theoretical approach to coding complex collections (such as my binary tree, which is really a self-balancing red-black-tree), then check out these links:

http://opendatastructures.org/versions/edition-0.1e/ods-java/6_2_BinarySearchTree_Unbala.html http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html

Happy coding :-)

Søren Fog http://iprotus.eu/

1.1 Create an empty stack

2.1 Do following while root is not NULL

a) Push root's right child and then root to stack.

b) Set root as root's left child.

2.2 Pop an item from stack and set it as root.

a) If the popped item has a right child and the right child 
   is at top of stack, then remove the right child from stack,
   push the root back and set root as root's right child.

b) Else print root's data and set root as NULL.

2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

Here is the Java implementation with two stacks

public static <T> List<T> iPostOrder(BinaryTreeNode<T> root) {
	if (root == null) {
		return Collections.emptyList();
	}
	List<T> result = new ArrayList<T>();
	Deque<BinaryTreeNode<T>> firstLevel = new LinkedList<BinaryTreeNode<T>>();
	Deque<BinaryTreeNode<T>> secondLevel = new LinkedList<BinaryTreeNode<T>>();
	firstLevel.push(root);
	while (!firstLevel.isEmpty()) {
		BinaryTreeNode<T> node = firstLevel.pop();
		secondLevel.push(node);
		if (node.hasLeftChild()) {
			firstLevel.push(node.getLeft());
		}
		if (node.hasRightChild()) {
			firstLevel.push(node.getRight());
		}
	}
	while (!secondLevel.isEmpty()) {
		result.add(secondLevel.pop().getData());			
	}		
	return result;
}

Here is the unit tests

@Test
public void iterativePostOrderTest() {
	BinaryTreeNode<Integer> bst = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});
	assertThat(BinaryTreeUtil.iPostOrder(bst).toArray(new Integer[0]), equalTo(new Integer[]{4,5,2,6,7,3,1}));
	
}

/**
 * This code will ensure holding of chain(links) of nodes from the root to till the level of the tree.
 * The number of extra nodes in the memory (other than tree) is height of the tree.
 * I haven't used java stack instead used this ParentChain. 
 * This parent chain is the link for any node from the top(root node) to till its immediate parent.
 * This code will not require any altering of existing BinaryTree (NO flag/parent on all the nodes).
 *  
 *  while visiting the Node 11; ParentChain will be holding the nodes 9 -> 8 -> 7 -> 1 where (-> is parent)
 *  
 *             1                               
              / \               
             /   \              
            /     \             
           /       \            
          /         \           
         /           \          
        /             \         
       /               \        
       2               7               
      / \             /         
     /   \           /          
    /     \         /           
   /       \       /            
   3       6       8               
  / \             /             
 /   \           /              
 4   5           9               
                / \             
                10 11
                     
 *               
 * @author ksugumar
 *
 */
public class InOrderTraversalIterative {
	public static void main(String[] args) {
		BTNode<String> rt;
		String[] dataArray = {"1","2","3","4",null,null,"5",null,null,"6",null,null,"7","8","9","10",null,null,"11",null,null,null,null};
		rt = BTNode.buildBTWithPreOrder(dataArray, new Counter(0));
		BTDisplay.printTreeNode(rt);
		inOrderTravesal(rt);
	}

public static void postOrderTravesal(BTNode<String> root) {
	ParentChain rootChain = new ParentChain(root);
	rootChain.Parent = new ParentChain(null);
	
	while (root != null) {
		
		//Going back to parent
		if(rootChain.leftVisited && rootChain.rightVisited) {
			System.out.println(root.data); //Visit the node.
			ParentChain parentChain = rootChain.Parent;
			rootChain.Parent = null; //Avoid the leak
			rootChain = parentChain;
			root = rootChain.root;
			continue;
		}
		
		//Traverse Left
		if(!rootChain.leftVisited) {
			rootChain.leftVisited = true;
			if (root.left != null) {
				ParentChain local = new ParentChain(root.left); //It is better to use pool to reuse the instances.
				local.Parent = rootChain;
				rootChain = local;
				root = root.left;
				continue;
			}
		} 
		
		//Traverse RIGHT
		if(!rootChain.rightVisited) {
			rootChain.rightVisited = true;
			if (root.right != null) {
				ParentChain local = new ParentChain(root.right); //It is better to use pool to reuse the instances.
				local.Parent = rootChain;
				rootChain = local;
				root = root.right;
				continue;
			}
		}
	}
}

class ParentChain {
	BTNode<String> root;
	ParentChain Parent;
	boolean leftVisited = false;
	boolean rightVisited = false;
	
	public ParentChain(BTNode<String> node) {
		this.root = node; 
	}
	
	@Override
	public String toString() {
		return root.toString();
	}
}

void display_without_recursion(struct btree **b) 
{
    deque< struct btree* > dtree;
        if(*b)
    dtree.push_back(*b);
        while(!dtree.empty() )
    {
        struct btree* t = dtree.front();
        cout << t->nodedata << " " ;
        dtree.pop_front();
        if(t->right)
        dtree.push_front(t->right);
        if(t->left)
        dtree.push_front(t->left);
    }
    cout << endl;
}

    import java.util.Stack;
   class Practice
{
    
    public static void main(String arr[])
	{
	    Practice prc = new Practice();
		TreeNode node1 = (prc).new TreeNode(1);
		TreeNode node2 = (prc).new TreeNode(2);
		TreeNode node3 = (prc).new TreeNode(3);
		TreeNode node4 = (prc).new TreeNode(4);
		TreeNode node5 = (prc).new TreeNode(5);
		TreeNode node6 = (prc).new TreeNode(6);
		TreeNode node7 = (prc).new TreeNode(7);
		node1.left = node2;
		node1.right = node3;
		node2.left = node4;
		node2.right = node5;
		node3.left = node6;
		node3.right = node7;
		postOrderIteratively(node1);
	}

	public static void postOrderIteratively(TreeNode root)
	{
		Stack<Entry> stack = new Stack<Entry>();
		Practice prc = new Practice();
		stack.push((prc).new Entry(root, false));
		while (!stack.isEmpty())
		{
			Entry entry = stack.pop();
			TreeNode node = entry.node;
			if (entry.flag == false)
			{
				if (node.right == null && node.left == null)
				{
					System.out.println(node.data);
				} else
				{
					stack.push((prc).new Entry(node, true));
					if (node.right != null)
					{
						stack.push((prc).new Entry(node.right, false));
					}
					if (node.left != null)
					{
						stack.push((prc).new Entry(node.left, false));
					}
				}
			} else
			{
				System.out.println(node.data);
			}
		}

	}
    
    class TreeNode
	{
		int data;
		int leafCount;
		TreeNode left;
		TreeNode right;

		public TreeNode(int data)
		{
			this.data = data;
		}

		public int getLeafCount()
		{
			return leafCount;
		}

		public void setLeafCount(int leafCount)
		{
			this.leafCount = leafCount;
		}

		public TreeNode getLeft()
		{
			return left;
		}

		public void setLeft(TreeNode left)
		{
			this.left = left;
		}

		public TreeNode getRight()
		{
			return right;
		}

		public void setRight(TreeNode right)
		{
			this.right = right;
		}

		@Override
		public String toString()
		{
			return "" + this.data;
		}
	}
	
	class Entry
	{
		Entry(TreeNode node, boolean flag)
		{
			this.node = node;
			this.flag = flag;
		}

		TreeNode node;
		boolean flag;

		@Override
		public String toString()
		{
			return node.toString();
		}
	}

    
}

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.

Here is a Python version too ::

class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

def postOrderIterative(root):

    if root is None :
        return

    s1 = []
    s2 = []
    s1.append(root)

    while(len(s1)>0):
        node = s1.pop()
        s2.append(node)

        if(node.left!=None):
            s1.append(node.left)

        if(node.right!=None):
            s1.append(node.right)

    while(len(s2)>0):
        node = s2.pop()
        print(node.data)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)

Here is the output ::

So you can use one stack to do a post order traversal.

private void PostOrderTraversal(Node pos) {
    Stack<Node> stack = new Stack<Node>();
    do {
        if (pos==null && (pos=stack.peek().right)==null) {
            for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
        } else if(pos!=null) {
            stack.push(pos);
            pos=pos.left;
        }
    } while (!stack.isEmpty());
}

Two methods to perform Post Order Traversal without Recursion:

1. Using One HashSet of Visited Nodes and One stack for backtracking:

   private void postOrderWithoutRecursion(TreeNode root) { if (root == null || root.left == null && root.right == null) { return; } Stack stack = new Stack<>(); Set visited = new HashSet<>(); while (!stack.empty() || root != null) { if (root != null) { stack.push(root); visited.add(root); root = root.left; } else { root = stack.peek(); if (root.right == null || visited.contains(root.right)) { System.out.print(root.val+" "); stack.pop(); root = null; } else { root = root.right; }

        }
    }
   

   }
   Time Complexity: O(n)
   Space Complexity: O(2n)
   
   

2. Using Tree Altering method:
   

   private void postOrderWithoutRecursionAlteringTree(TreeNode root) { if (root == null || root.left == null && root.right == null) { return; } Stack stack = new Stack<>(); while (!stack.empty() || root != null) { if (root != null) { stack.push(root); root = root.left; } else { root = stack.peek(); if (root.right == null) { System.out.print(root.val+" "); stack.pop(); root = null; } else { TreeNode temp = root.right; root.right = null; root = temp; } } } }
   Time Complexity: O(n)
   Space Complexity: O(n)
   

TreeNode Class:

public class TreeNode {
    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}

Here's a short (the walker is 3 lines) version that I needed to write in Python for a general tree. Of course, works for a more limited binary tree too. Tree is a tuple of the node and list of children. It only has one stack. Sample usage shown.

def postorder(tree):
    def do_something(x):  # Your function here
        print(x),
    def walk_helper(root_node, calls_to_perform):
        calls_to_perform.append(partial(do_something, root_node[0]))
        for child in root_node[1]:
            calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
    calls_to_perform = []
    calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
    while calls_to_perform:
        calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))

> d > c > b > a

The simplest solution, it may look like not the best answer but it is easy to understand. And I believe if you have understood the solution then you can modify it to make the best possible solution

// using two stacks

public List<Integer> postorderTraversal(TreeNode root){
 
 Stack<TreeNode> st=new Stack<>();
 Stack<TreeNode> st2=new Stack<>();
 ArrayList<Integer> al = new ArrayList<Integer>(); 
 
    if(root==null)
        return al;
    
 st.push(root);  //push the root to 1st stack

 while(!st.isEmpty())
 {
     TreeNode curr=st.pop();
     
     st2.push(curr);
     
     if(curr.left!=null)
        st.push(curr.left);
     if(curr.right!=null)
         st.push(curr.right);
     
 }
    
while(!st2.isEmpty())
    al.add(st2.pop().val);

//this ArrayList contains the postorder traversal

  return al;  
}

Simple Intuitive solution in python.

        while stack:
            node = stack.pop()
            if node:
                if isinstance(node,TreeNode):
                    stack.append(node.val)
                    stack.append(node.right)
                    stack.append(node.left)
                else:
                    post.append(node)
        return post

This is what I've come up for post order iterator:

    class PostOrderIterator
    implements Iterator<T> {

        private Stack<Node<T>> stack;
        private Node<T> prev;

        PostOrderIterator(Node<T> root) {
            this.stack = new Stack<>();
            recurse(root);
            this.prev = this.stack.peek();
        }

        private void recurse(Node<T> node) {
            if(node == null) {
                return;
            }

            while(node != null) {
                stack.push(node);
                node = node.left;
            }
            recurse(stack.peek().right);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public T next() {
            if(stack.peek().right != this.prev) {
                recurse(stack.peek().right);
            }

            Node<T> next = stack.pop();
            this.prev = next;
            return next.value;
        }
    }

Basically, the main idea is that you should think how the initialization process puts the first item to print on the top of the stack, while the rest of the stack follow the nodes that would have been touched by the recursion. The rest would just then become a lot easier to nail.

Also, from design perspective, PostOrderIterator is an internal class exposed via some factory method of the tree class as an Iterator<T>.

In post-order traversal, he left child of a node is visited first, followed by its right child, and finally the node itself. This tree traversal method is similar to depth first search (DFS) traversal of a graph.

Time Complexity: O(n)

Space Complexity: O(n)

Below is the iterative implementation of post-order traversal in python:

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

def post_order(node):
    if node is None:
        return []
    stack = []
    nodes = []
    last_node_visited = None
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek_node = stack[-1]
            if peek_node.right and last_node_visited != peek_node.right:
                node = peek_node.right
            else:
                nodes.append(peek_node.data)
                last_node_visited = stack.pop()
    return nodes

def main():
    '''
    Construct the below binary tree:

            15
           /  \
          /    \
         /      \
        10      20
       /  \    /  \
      8   12  16  25

    '''
    root = Node(15)
    root.left  = Node(10)
    root.right = Node(20)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(16)
    root.right.right = Node(25)
    print(post_order(root))


if __name__ == '__main__':
    main()

For writing iterative equivalents of these recursive methods, we can first understand how the recursive methods themselves execute over the program's stack. Assuming that the nodes do not have their parent pointer, we need to manage our own "stack" for the iterative variants.

One way to start is to see the recursive method and mark the locations where a call would "resume" (fresh initial call, or after a recursive call returns). Below these are marked as "RP 0", "RP 1" etc ("Resume Point"). For the case of postorder traversal:

void post(node *x)  
{  
  /* RP 0 */  
  if(x->lc) post(x->lc);  
  /* RP 1 */  
  if(x->rc) post(x->rc);  
  /* RP 2 */  
  process(x);  
}

Its iterative variant:

void post_i(node *root)  
{  
  node *stack[1000];  
  int top;  
  node *popped;  
 
  stack[0] = root;  
  top = 0;  
  popped = NULL;  
 
#define POPPED_A_CHILD() \  
  (popped && (popped == curr->lc || popped == curr->rc))  
 
  while(top >= 0)  
  {  
    node *curr = stack[top];  
 
    if(!POPPED_A_CHILD())  
    {  
      /* type (x: 0) */  
      if(curr->rc || curr->lc)  
      {  
        if(curr->rc) stack[++top] = curr->rc;  
 
        if(curr->lc) stack[++top] = curr->lc;  
 
        popped = NULL;  
        continue;  
      }  
    }  
 
    /* type (x: 2) */  
    process(curr);  
    top--;  
    popped = curr;  
  }  
}

The code comments with (x: 0) and (x: 2) correspond to the "RP 0" and "RP 2" resume points in the recursive method.

By pushing both the lc and rc pointers together, we have removed the need of keeping the post(x) invocation at resume-point 1 while the post(x->lc) completes its execution. That is, we could directly shift the node to "RP 2", bypassing "RP 1". So, there is no node kept on stack at "RP 1" stage.

The POPPED_A_CHILD macro helps us deduce one of the two resume-points ("RP 0", or "RP 2").