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:
- Create two empty Stacks.
- Push Root Node into first stack.
- Perform following operation, until first stack is not empty:
- Pop out top element from first stack and push it into second stack.
- Push Left node of popped node, if exists, into first stack.
- Push Right node of popped node, if exists, into second stack.
- 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:
- Inorder Tree Traversal Using Stack
- Preorder Tree Trasversal Using Stack
- Vertical Order Tree Traversal
- Top View of Binary Tree
- Bottom View of Binary Tree
- Delete Complete Binary Tree
- Check if two trees are mirror Trees of Each Other
- Convert Binary Tree to its Mirror Tree
- Check if Binary Tree is Symmetric or Not
- Print All Root to Leaf Paths in a Binary Tree
- Introduction to Tree Data Structure
- Binary Tree Traversals
- Print All Leaf Nodes of a Binary Tree
- Count Number of Nodes in a Binary Tree
- Print Alternate Levels of Binary Tree
- Maximum Width of Binary Tree
- Level Order Tree Traversal
- Left View of Binary Tree
- Right View of Binary Tree
- Compute Height of Binary Tree