# Postorder Traversal of Binary Tree Using Stacks

“Postorder Traversal of Binary Tree Using Stacks” is an important binary tree traversal algorithm. Here, we are given a binary tree and our task is to write a program to traverse the given binary tree in postorder manner using stack data structure.

We have already discussed recursive implementation of postorder traversal. Here, we will implement the iterative version of same recursive implementation using two stacks.

The steps required to implement postorder traversal of Binary Tree Using Stacks is as follows:

1. Create two empty Stacks.
2. Push Root Node into first stack.
3. Perform following operation, until first stack is not empty:
1. Pop out top element from first stack and push it into second stack.
2. Push Left node of popped node, if exists, into first stack.
3. Push Right node of popped node, if exists, into second stack.
4. Print all the elements of second stack.

#### C++ Program to implement postorder traversal of Binary Tree Using Stacks is as follows:

```/* C++ Program to implement postorder traversal of binary tree using stacks*/
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to implement Postorder Traversal */
void postorder(Node *root)
{
/* Check Base Condition */
if(root == NULL)
return;

/* Create an Empty Stack */
stack <Node *> st1, st2;

/* Push root Node into first stack */
st1.push(root);

while(!st1.empty())
{
/* Pop top node */
Node *temp = st1.top();
st1.pop();

/* Push Popped Node into second stack */
st2.push(temp);

/* Push Left Child, if exists */
if(temp -> left)
st1.push(temp -> left);

/* Push Right Child, if exists */
if(temp -> right)
st1.push(temp -> right);

}

/* Print Elements of second stack; which are stored in reverse postorder traversal */
while(!st2.empty())
{
Node *temp = st2.top();
cout<<temp -> data<<" ";
st2.pop();
}

}

int main()
{
/* Creating a Binary tree and inserting some nodes in it */
Node *root = NULL;

root = new Node(1);
root -> left = new Node(2);
root -> right = new Node(3);
root -> left -> left = new Node(4);
root -> left -> right = new Node(5);
root -> right -> left = new Node(6);
root -> right -> right = new Node (7);
root -> left -> right -> left = new Node(8);
root -> right -> left -> right = new Node(9);

/* Calling function to perform postorder traversal*/
cout<<"The Postorder Traversal of the Given Binary Tree is: ";
postorder(root);
}
```

OUTPUT:

`The Postorder Traversal of the Given Binary Tree is: 4 8 5 2 9 6 7 3 1`

Related Posts: