Perform PostOrder traversal on a Binary Tree by without Recursion

Question:

Given a binary tree root node, perform Post Order traversal by using stacks.

Example:

Consider the image given below:

PostOrder Traversal (Left, Right, Root): 7 15 10 18 30 25 16

Now lets see how to perform Post Order Traversal: (Left, Right, Root)

In Post-Order traversal, first Left node will be printed, then right node then the root node.

If we have only one node as below, we print that node.

If we have a tree with 3 nodes as below:

We can work it out with 2 stacks.

Stack 1 is used for node operation.
Stack 2 is used for display at the end.

Pass 1:

In the first pass, first we will inset the root node in stack 1.

Stack 1 = 16
Stack 2 = NULL

Now we will pop the first element form stack 1 and insert into stack 2.

Stack 1 = NULL
Stack 2 = 16

Then we go the left child and insert into the stack 1

Stack 1 = 10
Stack 2 = 16

Then we go the right child and insert into the stack 1

Stack 1 = 10,25
Stack 2 = 16

Pass 2:

In the second pass, pop the node from stack 1 and insert into stack 2.

Stack 1 = 10
Stack 2 = 16, 25

Now, check if there is left and right child of “node 25”, it’s not there. Hence move to the next pass.

Pass 3:

In the third pass, pop the node from stack 1 and insert into stack 2.

Stack 1 = NULL
Stack 2 = 16, 25, 10

Now, check if there is left and right child of “node 10”, it’s not there. Hence move to the next pass.

Now that we have completed the tree traversal, print the elements from the stack 2.

10, 25, 16. Hence post order traversal.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void print_post_order(struct Node *root) 
{ 

    stack<Node *> s_1; 
    stack<Node *> s_2; 
    Node *curr;

    s_1.push(root); 

    while (!s_1.empty()) 
    {   
        curr = s_1.top(); 
        s_1.pop();
        s_2.push(curr);

        if(curr->left != NULL) 
        {
            s_1.push(curr->left);
        }

        if(curr->right != NULL) 
        {
            s_1.push(curr->right);
        }
    } 

    while (s_2.empty() ==  false) 
    {   
        Node *curr = s_2.top(); 
        cout<<curr->data <<" ";
        s_2.pop(); 
    }
} 


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"Post Order Traversal(Left, Root, Right) = " ; print_post_order(root); 


    return 0;  
}  

 

Output:

Post Order Traversal(Left, Root, Right) = 7 15 10 18 30 25 16