Binary Tree Post-Order Traversal Iterative Solution

Given a binary tree, print the elements in post-order iteratively without using recursion.


We know the elements can be printed post-order easily using recursion, as follow:

This is the most difficult of all types of iterative tree traversals. You should attempt this problem: Binary Search Tree In-Order Traversal Iterative Solution before this as it is an easier problem. The easiest of all iterative tree traversals is Pre-Order Traversal.

Post-order traversal is useful in some types of tree operations:

  1. Tree deletion. In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node can only be deleted when both of its left and right subtrees are deleted.
  2. Evaluating post-fix notation.

If you keep visited flags in the binary tree while traversing, the problem could be solved in a more direct manner. But we will not discuss this solution here, as it has already been discussed in Wikipedia’s article on Tree Traversal. Here, we discuss a solution without using any visited flags, which seems challenging to solve.

Hint:
As usual, a stack-based solution is necessary when there is no parent pointer available in the tree. Try to follow the post-order traversal of a sample binary tree. When should you print a node’s value? Note under what condition it traverses up/down the tree. Try to use a variable to store the previously-traversed node. How would it help when it traverses up/down the tree?

Post-order traversal sequence: A, C, E, D, B, H, I, G, F

Solution:
We use a prev variable to keep track of the previously-traversed node. Let’s assume curr is the current node that’s on top of the stack. When prev is curr‘s parent, we are traversing down the tree. In this case, we try to traverse to curr‘s left child if available (ie, push left child to the stack). If it is not available, we look at curr‘s right child. If both left and right child do not exist (ie, curr is a leaf node), we print curr‘s value and pop it off the stack.

If prev is curr‘s left child, we are traversing up the tree from the left. We look at curr‘s right child. If it is available, then traverse down the right child (ie, push right child to the stack), otherwise print curr‘s value and pop it off the stack.

If prev is curr‘s right child, we are traversing up the tree from the right. In this case, we print curr‘s value and pop it off the stack.

The above method is easy to follow, but has some redundant code. We could refactor out the redundant code, and now it appears to be more concise. Note how the code section for printing curr‘s value get refactored into one single else block. Don’t worry about in an iteration where its value won’t get printed, as it is guaranteed to enter the else section in the next iteration.

Alternative Solution:
An alternative solution is to use two stacks. Try to work it out on a piece of paper. I think it is quite magical and beautiful. You will think that it works magically, but in fact it is doing a reversed pre-order traversal. That is, the order of traversal is a node, then its right child followed by its left child. This yields post-order traversal in reversed order. Using a second stack, we could reverse it back to the correct order.

Here is how it works:

  1. Push the root node to the first stack.
  2. Pop a node from the first stack, and push it to the second stack.
  3. Then push its left child followed by its right child to the first stack.
  4. Repeat step 2) and 3) until the first stack is empty.
  5. Once done, the second stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the second stack one by one and you’re done.

Complexity Analysis:
The two-stack solution takes up more space compared to the first solution using one stack. In fact, the first solution has a space complexity of O(h), where h is the maximum height of the tree. The two-stack solution however, has a space complexity of O(n), where n is the total number of nodes.

VN:F [1.9.22_1171]
Rating: 4.8/5 (85 votes cast)
Binary Tree Post-Order Traversal Iterative Solution, 4.8 out of 5 based on 85 ratings

68 thoughts on “Binary Tree Post-Order Traversal Iterative Solution

    1. daniel008

      struct Node
      {
      int m_value;
      Node* m_left;
      Node* m_right;
      };
      tyepdef std::pair Data;

      void PostTraverse(Node* d)
      {
      stack s;
      if (d) s.push(Data(d, true));

      while (!s.empty())
      {
      Data t = s.pop();
      if (t.second)
      {
      s.push(Data(t.first, false;))
      if (t.first->m_right)
      s.push(Data(t.first->m_right, true));
      if (t.first->m_left)
      s.push(Data(t.first->m_left, true));
      }
      else
      {
      std::cout <m_value;
      }

      }

      }

      VA:F [1.9.22_1171]
      -3
  1. Abhishek Jain

    Another way of doing PostOrder Iterative traversal using two stacks

    Here I have taken other childStack to store right child of each node.

    public class PostOrderItr2
    {
    static StackLL stack;
    static StackLL childStack;

    public static void postOrderTrav(Node node)
    {
    stack = new StackLL();
    childStack = new StackLL();

    if(node == null)
    {
    return;
    }
    while(true)
    {
    if(node != null)
    {
    stack.push(node);
    if(node.right != null)
    {
    childStack.push(node.right);
    }
    node = node.left;
    }
    else if(!stack.isEmpty())
    {
    Node parent = stack.peek();

    if(!childStack.isEmpty() && parent.right == childStack.peek())
    {
    node = childStack.pop();
    }
    else
    {
    stack.pop();
    System.out.print(" " + parent.data);
    }
    }
    else
    {
    return;
    }
    }
    }
    }

    VA:F [1.9.22_1171]
    +2
  2. Tracy

    @1337c0d3r:
    I'm quite sure that my code of using one stack for post-order traversal works. You can use the same example above to go through it. I made iterative in-order, pre-order and post-order traversal as similar as possible:

    void postorderNoR(const Node *root)
    {
    stack s;
    const Node *itr = root;

    while (itr || !s.empty()) {
    if (!itr) {
    while (!s.empty() &&
    itr == s.top()->right) {
    itr = s.top();
    s.pop();
    printf("%d ",itr->value);
    }
    itr = s.empty() ? NULL : s.top()->right;
    }
    else
    {
    s.push(itr);
    itr = itr->left;
    }
    }
    }

    // *********************

    void inorderNoR(const Node *root)
    {
    stack s;
    const Node *itr = root;

    while (itr || !s.empty()){
    if (!itr){
    itr = s.top();
    s.pop();
    printf("%d ",itr->value);
    itr = itr->right;
    }
    else{
    s.push(itr);
    itr = itr->left;
    }
    }
    }

    // *********************

    void preorderNoR(const Node *root)
    {
    stack s;
    const Node *itr = root;

    while (itr || !s.empty()){
    if (!itr){
    itr = s.top();
    s.pop();
    itr = itr->right;
    }
    else{
    printf("%d ",itr->value);
    s.push(itr);
    itr = itr->left;
    }
    }
    }

    VA:F [1.9.22_1171]
    0
  3. arnimarj

    A python solution which stores a state with each stack entry, showing which of two children to push next

    def post_order_b_(root):
    ….if root == None:
    ……..return

    ….stack = [[root, 0]]

    ….while len(stack) > 0:
    ……..node, state = stack[-1]

    ……..if state == 2:
    …………visit(node)
    …………stack.pop()
    ……..else:
    …………child = (node.GetLeft() if state == 0 else node.GetRight())

    …………stack[-1][1] += 1

    …………if child != None:
    …………….stack.append([child, 0])

    VA:F [1.9.22_1171]
    0
  4. gt

    There is something called MORRIS inorder traversal which does not require any stack usage to perform the traversal… it uses a tree-transformation technique to get the traversal done iteratively … not sure if we could tweak it for post or pre-order traversal … i vaguely recollect it is not possible for some reason … although i am not sure myself …

    why cant we try and come up with an approach that doesnt involve usage of stack per se ? … because if we do, we are merely mimicking the recursive approach….

    VA:F [1.9.22_1171]
    -1
  5. codingC

    @1337c0d3r:
    Thank you for the excellent solution. The two stack solution is indeed brilliant. But it seems to me not a reversed pre-order traversal as what you mentioned.

    VA:F [1.9.22_1171]
    -1
  6. amal

    hi, can you help me to solve this question plese:

    write a c-program to arrange the inputted data item on root and other items on left or right nodes of the binary tree. that program should also provide to display the following functions:
    1.in order traversal
    2.pre order traversal
    3.post order traversal
    4.exit

    VA:F [1.9.22_1171]
    0
  7. Bala

    @1337c0d3r:

    Thank you so much for the post; the explanation articulates your solution in a very neat manner.

    VA:F [1.9.22_1171]
    0
  8. Nathan

    I guess an easy way to do this is that, every time you push a node to the stack, push it twice. The first one is used to simulate the function call, the second is to simulate the function frame:

    VA:F [1.9.22_1171]
    +2
    1. Nathan

      sorry, formated code:

      VA:F [1.9.22_1171]
      +2
  9. Kshitij

    I went through your iterative inorder traversal page and tried to write the post order one and I guess i have got a bit simpler code than the one mentioned here. See if you can edit the post to include this for other users:

    public void postOrder_iterative(Tree root){
    Stack s = new Stack();
    Tree current = root;
    Tree prevElement = null;
    while(!s.empty() || current !=null){
    if(current !=null){
    s.push(current);
    current = current.left;
    }else{
    current = s.lastElement();
    if(current.right == null || current.right == prevElement){
    System.out.println(current.value);
    prevElement = current;
    s.pop();
    current = null;
    }else{
    current = current.right;
    }
    }
    }
    }

    VA:F [1.9.22_1171]
    0
    1. Kshitij

      public void postOrder_iterative(Tree root){
      Stack s = new Stack();
      Tree current = root;
      Tree prevElement = null;
      while(!s.empty() || current !=null){
      if(current !=null){
      s.push(current);
      current = current.left;
      }else{
      current = s.lastElement();
      if(current.right == null || current.right == prevElement){
      System.out.println(current.value);
      prevElement = current;
      s.pop();
      current = null;
      }else{
      current = current.right;
      }
      }
      }
      }

      VA:F [1.9.22_1171]
      -1
  10. Karthick

    Well, can the preorder traversal be done this way. I tried a few cases and it seemed to be alright.

    This way, it seems like we have to push only the right child of every node.

    Is this correct?

    VA:F [1.9.22_1171]
    0
  11. Pingback: Binary Tree Post-Order Traversal Iterative Solution | 口├人人│의 Blog

  12. prasad

    Hi, i came up with this solution. With my initial testing it seems working fine. Can you please take a look at it. Thanks.

    void postorder(node* root)
    {
    if(!root) return;
    stack s;
    bool FirstTime = true;
    node* r = root;
    node *q, *last_q;
    last_q = null;

    while(!s.IsEmpty() || FirstTime)
    {
    FirstTime = false;
    while(r != null)
    {
    s.push(r);
    r = r->left;
    }

    q = s.pop();
    if(q->right == NULL || q->right == last_q)
    {
    print(q->data);
    last_q = q;
    }
    else
    {
    s.push(q);
    r = r->right;
    }
    }
    }

    VA:F [1.9.22_1171]
    0
  13. Profile photo of harelgharelg

    another solution:
    you can always kinda cheat your way around with pushing a dummy node right after you push yourself down the stack.
    every node except a leaf would be pushed once by its parent and once by itself (after pushing right then left children then dummy)
    and when you pop a dummy you pop another one and print

    VN:F [1.9.22_1171]
    0
  14. stv

    The 3rd way is brilliant. Thanks for good explanation. I guess the order to push the left/right child nodes to the tree for the first stack should be swapped, so that when we print, we print left-right-root instead of right-left-root.

    VA:F [1.9.22_1171]
    0
  15. et

    For the two stack solution. I think this step is reversed.
    3) Then push its left child followed by its right child to the first stack.

    It should be push it right child followed by its left child.

    VA:F [1.9.22_1171]
    0
  16. Profile photo of SGSG

    pseudo code:

    Stack s=new Stack();
    s.push(root);

    do
    {
    if(root->left !=NULL && root->left->visited==false)
    {
    stack.push(root->left);
    root=stack.top;
    continue;
    }

    if(root->right!=NULL && root->right->visited==false)
    {
    stack.push(root->right);
    root=stack.top;
    continue;
    }

    stack.peek().visited=true;
    display(stack.top);
    stack.pop();
    root=stack.peek();
    }while(stack.peek()!=empty)

    I just push in the root first into the stack. Along with the key value at each node I also maintain a visited flag to not get caught up into a loop wherein I am traversing the same node again and again. As soon as both the if conditions I have mentioned become invalid, I pop off the node from the stack, ultimately achieveing post order traversal.

    Please leave your valuable feedback. I think this works, but if there are any mistakes please point me to them..

    VN:F [1.9.22_1171]
    0
  17. Pingback: Iterative Pre-order In-order Post-order Traversal (with Stack) | This is how Cheng grows up

  18. Frankie

    Can the below code work?
    void PostOrder(TreeNode* pRoot)
    {
    if(pRoot == NULL)
    return;

    TreeNode* pNode = pRoot;
    TreeNode* pPrev = NULL; // latest visited node
    stack st;
    while(pNode != NULL || !st.empty())
    {
    while(pNode != NULL)
    {
    st.push(pNode);
    pNode = pNode -> left;
    }

    pNode = st.top();
    // node has no right child or right child has just been visited
    if(pNode -> right == NULL || pNode -> right == pPrev)
    {
    visit(pNode);
    st.pop();
    pPrev = pNode;
    pNode = NULL;
    }
    else
    {
    pNode = pNode -> right;
    }
    }
    }

    VA:F [1.9.22_1171]
    0
  19. zyfo2

    we can change the iterative inorder traversal a little bit to work for postorder
    public static ArrayList inorderTraversal(TreeNode root) {
    ArrayList l=new ArrayList();
    Stack s=new Stack();
    TreeNode current=root;
    boolean child=false;
    while(!s.isEmpty()||current!=null){
    if(current!=null){
    s.push(current);
    current=current.left;
    child=false;
    }
    else{
    current=s.peek();
    if(!child){current=current.right;child=true;}
    else{current=s.pop(); l.add(current.val);
    if(!s.isEmpty()&&current==s.peek().left){child=false;}
    else if(!s.isEmpty()&&current==s.peek().right){child=true;}
    current=null;
    }
    }
    }
    return l;
    }

    VA:F [1.9.22_1171]
    +1
  20. Profile photo of aaaaaaamieaaaaaaamie

    The two stack solution is awesome.
    I’ve got a short working version in Java:

    while(!stack.isEmpty()) {
    TreeNode cur = stack.peek();
    if(cur == null) stack.pop();

    // not popping this one yet
    else if(cur.right != prev) {
    if(cur.left == prev)
    stack.push(cur.right);
    else
    stack.push(cur.left);
    }
    else {
    output.add(stack.pop().val);
    }
    prev = cur;
    }

    VN:F [1.9.22_1171]
    0
  21. lcn

    Haven’t read all the comments, maybe someone has already did this: use one stack, and if a popped node doesn’t satisfy the print condition, push it back to the stack again before pushing its children.

    VA:F [1.9.22_1171]
    0
  22. bcorso

    There are a couple of solutions for this with slightly different if conditions. This solution makes the most since to me:

    public static List postOrderTraversal(Node root){
    List list = new ArrayList();
    Node prev, curr;
    Deque stack = new ArrayDeque();
    stack.push(root)
    while( !stack.isEmpty() ){
    curr = stack.peek();
    //Going left
    if(curr.left != null && curr.left != prev && (curr.right != prev || prev == null))
    stack.push(curr.left);
    //Can't go left, go right
    else if(curr.right != null && curr.right != prev)
    stack.push(curr.right);
    //Can't go left or right, go up (pop)
    else{
    prev = stack.pop();
    list.add(prev.key);
    }
    }
    return list;
    }

    VA:F [1.9.22_1171]
    0
    1. bcorso

      Testing stupid syntax

      VA:F [1.9.22_1171]
      0
      1. bcorso

        For anyone interested, you need to close the code tag

        VA:F [1.9.22_1171]
        0
  23. GM

    Algo for non recursive post orde traversal
    1.ptr=ROOT
    2.f=0
    3.push(NULL)
    4.while(TOP!=-1) do
    5. while(ptr!=NULL && f==0) do
    6. push(1)
    7. push(ptr)
    8. ptr=ptr->lchild
    9. Endwhile
    10. ptr=pop()
    11. f=pop()
    12. if(f==1)
    13. push(2)
    14. push(ptr)
    15. ptr=ptr->rchild
    16. f=0
    17. else if(ptr->data!=NULL)
    18. visit(ptr->data)
    19. Endif
    20. Endif
    21. Endwhile
    22. stop

    VA:F [1.9.22_1171]
    0
  24. Ashwin

    I am not able to explain a part of code in first method.

    I think it always enters the IF statement

    In your example, once F,B and A are pushed into stack,
    we print A and pop A
    Now,

    and in next loop

    becomes B
    Here, it will again enter the IF loop when it shouldnt. Could you please explain why it doesn’t?

    Thanks

    VA:F [1.9.22_1171]
    0
  25. jaro

    VA:F [1.9.22_1171]
    0
  26. luyao

    VA:F [1.9.22_1171]
    0
  27. Suhail Rather

    VA:F [1.9.22_1171]
    +1
  28. Suhail Rather

    VA:F [1.9.22_1171]
    +1
  29. Wei Qiu

    Another solution is a plain mimic of how the call stack works.
    We put some extra information on the stack to indicate whether the call is returned or not.

    [code]
    struct Frame{
    public:
    bool called;
    TreeNode * cur;

    Frame(TreeNode* curp):called(false), cur(curp){}
    };

    class Solution {
    public:
    vector postorderTraversal(TreeNode *root) {
    vector result;
    stack callstack;
    Frame rootf(root);
    callstack.push(rootf);
    bool called;
    while(!callstack.empty()){
    TreeNode *cur = callstack.top().cur;
    called = callstack.top().called;
    if(!called){
    callstack.top().called = true;
    if(cur->right == NULL && cur->left == NULL){
    result.push_back(cur->val);
    callstack.pop();
    }else{
    if(cur->right != NULL){
    Frame newf(cur->right);
    callstack.push(newf);
    }
    if(cur->left != NULL){
    Frame newf(cur->left);
    callstack.push(newf);
    }
    }
    }else{
    result.push_back(cur->val);
    callstack.pop();
    }
    }
    return result;
    }
    };

    [/code]

    VA:F [1.9.22_1171]
    0
    1. Wei Qiu

      VA:F [1.9.22_1171]
      0
  30. Srini

    I believe the below should PO traversal of a binary tree. Please let me know if you have any comments.

    VA:F [1.9.22_1171]
    0
  31. Srini

    Having issues with posting the full code as this blog does not accept a few characters, so I updated a few lines to pseudo-code.

    The below code should do a Post-Order traversal of a Binary Tree. Please let me know if you have any comments.

    VA:F [1.9.22_1171]
    0
  32. Pingback: Binary Tree In-order, Pre-order and Post-order Traversal: Iterative way | Kaituo

  33. Profile photo of AnuAnu

    I tried to come with a solution that perform generic iterative tree traversal. When doing a generic tree traversal each node will be visited 3 times, from the top, from the left and from the right.

    If we process each node data when its visited from the right, its postorder
    If we process each node data when its visited from the top, its preorder
    If we process each node data when its visited from the left, its inorder

    VN:F [1.9.22_1171]
    +2
  34. Pingback: 3 ways of iterative post-order traversal | Changhaz's Codeplay

  35. Pingback: 教你如何迭代地遍历二叉树 | 易鸣

  36. zxcve

    Simpler solution via single stack:

    static void display_postorder_withstack(node *head)
    {
    ll_node1 *stack = NULL;
    bool done = false;
    node *prev = NULL;

    while (!done)
    {
    if (head)
    {
    push1 (&stack, head);
    prev = head;
    head = head->left;
    }
    else
    {
    head = pop1(&stack);
    if (head && prev != head->right)
    {
    if (!head->right)
    {
    printf(“%d “, head->data);
    prev = head;
    }
    else
    push1 (&stack, head);

    head = head->right;
    }
    else if (head)
    {
    printf(“%d “, head->data);
    prev = head;
    head = NULL;
    }
    else
    done = true;
    }
    }
    }

    Repush the root if found that prev pointer was root->right ,otherwise print the root and make root as NULL.

    VA:F [1.9.22_1171]
    0
  37. Pingback: leetcode: Binary Tree Postorder Traversal Solution Analysis 2 | 烟客旅人 sigmainfy

  38. Profile photo of RalphRalph

    mine. hope it helps

    VN:F [1.9.22_1171]
    0
  39. Mike

    VA:F [1.9.22_1171]
    0
  40. Profile photo of LokiLoki

    A complete implementation in C.
    Uses very minimal special cases etc… just prints in one single place…

    The main invariant at the start of the loop is that “temp” is the current node that is being processed, and is not
    already in the stack. if “temp” is NULL, that just means we need to pop something out of the stack (possibly..)

    VN:F [1.9.22_1171]
    0
  41. Pingback: 二叉树后序遍历的非递归实现 | 书影博客

  42. Messi Tiger

    VA:F [1.9.22_1171]
    0
  43. patrick

    Thanks for sharing the ideas.
    In one stack method, I believe we should push right child first, then the left child.
    Correct me if I’m wrong.

    VA:F [1.9.22_1171]
    0
  44. Profile photo of madnomadno

    We can simplify the code by keeping the following invariant: “the cursor should never be null”.

    VN:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.