Binary Tree Post-Order Traversal Iterative Solution

October 27, 2010 in binary tree

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 (66 votes cast)
Binary Tree Post-Order Traversal Iterative Solution, 4.8 out of 5 based on 66 ratings

57 responses to Binary Tree Post-Order Traversal Iterative Solution

  1. nice post.
    So, what is the time complexity of these 3 methods?

    VA:F [1.9.22_1171]
    +1
    • 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]
      -2
  2. All of them runs in O(N) time complexity, where N is the total number of nodes.

    VA:F [1.9.22_1171]
    +2
  3. 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
  4. Great idea of using two stacks, it is very easy to understand and implement, thank you

    VA:F [1.9.22_1171]
    +2
  5. @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
  6. @1337c0d3r:
    Er… How to post the source code as the way you did in the main post?

    VA:F [1.9.22_1171]
    0
  7. @Tracy:
    There's no easy way to do this now in Blogger (Blogger will automatically discard some symbols in the comment). Could you paste your code here?

    http://ideone.com/

    VA:F [1.9.22_1171]
    -2
  8. @1337c0d3r:

    I just posted them here:

    https://ideone.com/g17bt

    VA:F [1.9.22_1171]
    -1
  9. @Tracy:
    Cool! Thanks for sharing, I'll look into it soon :)

    VA:F [1.9.22_1171]
    -1
  10. 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
  11. 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
  12. @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
  13. 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
  14. @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
  15. 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
    • sorry, formated code:

      VA:F [1.9.22_1171]
      +1
  16. 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
    • 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
  17. 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
  18. Another solution which uses extra space than first solution mentioned above but does it using single stack http://tryingout101.blogspot.com/2011/08/iterative-postorder-of-binary-tree-part.html

    VA:F [1.9.22_1171]
    0
  19. For method 2 , complxity shud be O(n) ..how is it O(h) or O(logn) ..please explain …

    VA:F [1.9.22_1171]
    0
  20. 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
  21. 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
  22. stv said on July 3, 2012

    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]
    -1
  23. et said on July 26, 2012

    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]
    -1
  24. 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
  25. Nice blog!

    VN:F [1.9.22_1171]
    0
  26. 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
  27. 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
  28. The second solution is absolutely brilliant!!!

    VA:F [1.9.22_1171]
    0
  29. 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
  30. This is the initial and most common purpose for avoiding meals.

    VA:F [1.9.22_1171]
    0
  31. 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
  32. 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
    • Testing stupid syntax

      VA:F [1.9.22_1171]
      0
      • For anyone interested, you need to close the code tag

        VA:F [1.9.22_1171]
        0
  33. 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
  34. 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
  35. VA:F [1.9.22_1171]
    0
  36. templates were destroyed when I posted it. I do not want to check how to fix it. just see this https://ideone.com/Y34M6q
    best
    js

    VA:F [1.9.22_1171]
    0
  37. VA:F [1.9.22_1171]
    0
  38. VA:F [1.9.22_1171]
    +1
  39. VA:F [1.9.22_1171]
    +1
  40. good explanation. easy to understand!
    Thanks a lot!

    VA:F [1.9.22_1171]
    0
  41. 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
    • VA:F [1.9.22_1171]
      0
  42. Is Post order traversal is possible without using stack and recursion?

    VA:F [1.9.22_1171]
    0
  43. 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
  44. 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
  45. 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
  46. 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
  47. mine. hope it helps

    VN:F [1.9.22_1171]
    0
  48. VA:F [1.9.22_1171]
    0
  49. 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

Leave a reply

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

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