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.

Postorder Traversal of Binary Tree Using Stacks
Postorder Tree Traversal

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:

  1. Inorder Tree Traversal Using Stack
  2. Preorder Tree Trasversal Using Stack
  3. Vertical Order Tree Traversal
  4. Top View of Binary Tree
  5. Bottom View of Binary Tree
  6. Delete Complete Binary Tree
  7. Check if two trees are mirror Trees of Each Other
  8. Convert Binary Tree to its Mirror Tree
  9. Check if Binary Tree is Symmetric or Not
  10. Print All Root to Leaf Paths in a Binary Tree
  11. Introduction to Tree Data Structure
  12. Binary Tree Traversals
  13. Print All Leaf Nodes of a Binary Tree
  14. Count Number of Nodes in a Binary Tree
  15. Print Alternate Levels of Binary Tree
  16. Maximum Width of Binary Tree
  17. Level Order Tree Traversal
  18. Left View of Binary Tree
  19. Right View of Binary Tree
  20. Compute Height of Binary Tree

You may also like...