Iterative Postorder Traversal | Set 1 (Using Two Stacks)

Last Updated : 11 Sep, 2023

We have discussed iterative inorder and iterative preorder traversals. In this post, iterative postorder traversal is discussed, which is more complex than the other two traversals (due to its nature of non-tail recursion, there is an extra statement after the final recursive call to itself). Postorder traversal can easily be done using two stacks, though. The idea is to push reverse postorder traversal to a stack. Once we have the reversed postorder traversal in a stack, we can just pop all items one by one from the stack and print them; this order of printing will be in postorder because of the LIFO property of stacks. Now the question is, how to get reversed postorder elements in a stack – the second stack is used for this purpose. For example, in the following tree, we need to get 1, 3, 7, 6, 2, 5, 4 in a stack. If we take a closer look at this sequence, we can observe that this sequence is very similar to the preorder traversal. The only difference is that the right child is visited before left child, and therefore the sequence is “root right left” instead of “root left right”. So, we can do something like iterative preorder traversal with the following differences:
a) Instead of printing an item, we push it to a stack.
b) We push the left subtree before the right subtree.
Following is the complete algorithm. After step 2, we get the reverse of a postorder traversal in the second stack. We use the first stack to get the correct order.

1. Push root to first stack.
2. Loop while first stack is not empty
   2.1 Pop a node from first stack and push it to second stack
   2.2 Push left and right children of the popped node to first stack
3. Print contents of second stack

Let us consider the following tree

Following are the steps to print postorder traversal of the above tree using two stacks.

1. Push 1 to first stack.
      First stack: 1
      Second stack: Empty

2. Pop 1 from first stack and push it to second stack. 
   Push left and right children of 1 to first stack
      First stack: 2, 3
      Second stack: 1

3. Pop 3 from first stack and push it to second stack. 
   Push left and right children of 3 to first stack
      First stack: 2, 6, 7
      Second stack: 1, 3

4. Pop 7 from first stack and push it to second stack.
      First stack: 2, 6
      Second stack: 1, 3, 7

5. Pop 6 from first stack and push it to second stack.
      First stack: 2
      Second stack: 1, 3, 7, 6

6. Pop 2 from first stack and push it to second stack. 
   Push left and right children of 2 to first stack
      First stack: 4, 5
      Second stack: 1, 3, 7, 6, 2

7. Pop 5 from first stack and push it to second stack.
      First stack: 4
      Second stack: 1, 3, 7, 6, 2, 5

8. Pop 4 from first stack and push it to second stack.
      First stack: Empty
      Second stack: 1, 3, 7, 6, 2, 5, 4

The algorithm stops here since there are no more items in the first stack. 
Observe that the contents of second stack are in postorder fashion. Print them.

Following is the implementation of iterative postorder traversal using two stacks.

C++

#include <bits/stdc++.h> 
using namespace std; 
  
// A tree node 
struct Node { 
  
    int data; 
    Node *left, *right; 
}; 
  
// Function to create a new node with the given data 
Node* newNode(int data) 
{ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
// An iterative function to do post order 
// traversal of a given binary tree 
void postOrderIterative(Node* root) 
{ 
    if (root == NULL) 
        return; 
  
    // Create two stacks 
    stack<Node *> s1, s2; 
  
    // push root to first stack 
    s1.push(root); 
    Node* node; 
  
    // Run while first stack is not empty 
    while (!s1.empty()) { 
        // Pop an item from s1 and push it to s2 
        node = s1.top(); 
        s1.pop(); 
        s2.push(node); 
  
        // Push left and right children 
        // of removed item to s1 
        if (node->left) 
            s1.push(node->left); 
        if (node->right) 
            s1.push(node->right); 
    } 
  
    // Print all elements of second stack 
    while (!s2.empty()) { 
        node = s2.top(); 
        s2.pop(); 
        cout << node->data << " "; 
    } 
} 
  
// Driver code 
int main() 
{ 
    // Let us construct the tree 
    // shown in above figure 
    Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
  
    postOrderIterative(root); 
  
    return 0; 
} 

C

#include <stdio.h> 
#include <stdlib.h> 
  
// Maximum stack size 
#define MAX_SIZE 100 
  
// A tree node 
struct Node { 
    int data; 
    struct Node *left, *right; 
}; 
  
// Stack type 
struct Stack { 
    int size; 
    int top; 
    struct Node** array; 
}; 
  
// A utility function to create a new tree node 
struct Node* newNode(int data) 
{ 
    struct Node* node = (struct Node*)malloc(sizeof(struct Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
  
// A utility function to create a stack of given size 
struct Stack* createStack(int size) 
{ 
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); 
    stack->size = size; 
    stack->top = -1; 
    stack->array = (struct Node**)malloc(stack->size * sizeof(struct Node*)); 
    return stack; 
} 
  
// BASIC OPERATIONS OF STACK 
int isFull(struct Stack* stack) 
{ 
    return stack->top - 1 == stack->size; 
} 
  
int isEmpty(struct Stack* stack) 
{ 
    return stack->top == -1; 
} 
  
void push(struct Stack* stack, struct Node* node) 
{ 
    if (isFull(stack)) 
        return; 
    stack->array[++stack->top] = node; 
} 
  
struct Node* pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return NULL; 
    return stack->array[stack->top--]; 
} 
  
// An iterative function to do post order traversal of a given binary tree 
void postOrderIterative(struct Node* root) 
{ 
    if (root == NULL) 
        return; 
  
    // Create two stacks 
    struct Stack* s1 = createStack(MAX_SIZE); 
    struct Stack* s2 = createStack(MAX_SIZE); 
  
    // push root to first stack 
    push(s1, root); 
    struct Node* node; 
  
    // Run while first stack is not empty 
    while (!isEmpty(s1)) { 
        // Pop an item from s1 and push it to s2 
        node = pop(s1); 
        push(s2, node); 
  
        // Push left and right children of removed item to s1 
        if (node->left) 
            push(s1, node->left); 
        if (node->right) 
            push(s1, node->right); 
    } 
  
    // Print all elements of second stack 
    while (!isEmpty(s2)) { 
        node = pop(s2); 
        printf("%d ", node->data); 
    } 
} 
  
// Driver program to test above functions 
int main() 
{ 
    // Let us construct the tree shown in above figure 
    struct Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
  
    postOrderIterative(root); 
  
    return 0; 
} 

Java

// Java program for iterative post 
// order using two stacks 
  
import java.util.*; 
public class IterativePostorder { 
  
    static class node { 
        int data; 
        node left, right; 
  
        public node(int data) 
        { 
            this.data = data; 
        } 
    } 
  
    // Two stacks as used in explanation 
    static Stack<node> s1, s2; 
  
    static void postOrderIterative(node root) 
    { 
        // Create two stacks 
        s1 = new Stack<>(); 
        s2 = new Stack<>(); 
  
        if (root == null) 
            return; 
  
        // push root to first stack 
        s1.push(root); 
  
        // Run while first stack is not empty 
        while (!s1.isEmpty()) { 
            // Pop an item from s1 and push it to s2 
            node temp = s1.pop(); 
            s2.push(temp); 
  
            // Push left and right children of 
            // removed item to s1 
            if (temp.left != null) 
                s1.push(temp.left); 
            if (temp.right != null) 
                s1.push(temp.right); 
        } 
  
        // Print all elements of second stack 
        while (!s2.isEmpty()) { 
            node temp = s2.pop(); 
            System.out.print(temp.data + " "); 
        } 
    } 
  
    public static void main(String[] args) 
    { 
        // Let us construct the tree 
        // shown in above figure 
  
        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); 
  
        postOrderIterative(root); 
    } 
} 
  
// This code is contributed by Rishabh Mahrsee 

Python3

# Python program for iterative postorder  
# traversal using two stacks 
  
# A binary tree node 
class Node: 
      
    # Constructor to create a new node 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
  
# An iterative function to do postorder  
# traversal of a given binary tree 
def postOrderIterative(root):  
  
    if root is None: 
        return        
      
    # Create two stacks  
    s1 = [] 
    s2 = [] 
      
    # Push root to first stack 
    s1.append(root) 
      
    # Run while first stack is not empty 
    while s1: 
          
        # Pop an item from s1 and  
        # append it to s2 
        node = s1.pop() 
        s2.append(node) 
      
        # Push left and right children of  
        # removed item to s1 
        if node.left: 
            s1.append(node.left) 
        if node.right: 
            s1.append(node.right) 
  
        # Print all elements of second stack 
    while s2: 
        node = s2.pop() 
        print(node.data,end=" ") 
  
# Driver program to test above function 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
root.right.left = Node(6) 
root.right.right = Node(7) 
postOrderIterative(root) 

C#

// C# program for iterative post 
// order using two stacks 
using System; 
using System.Collections; 
public class IterativePostorder { 
  
    public class node { 
        public int data; 
        public node left, right; 
  
        public node(int data) 
        { 
            this.data = data; 
        } 
    } 
  
    // Two stacks as used in explanation 
    static public Stack s1, s2; 
  
    static void postOrderIterative(node root) 
    { 
        // Create two stacks 
        s1 = new Stack(); 
        s2 = new Stack(); 
  
        if (root == null) 
            return; 
  
        // Push root to first stack 
        s1.Push(root); 
  
        // Run while first stack is not empty 
        while (s1.Count > 0) { 
            // Pop an item from s1 and Push it to s2 
            node temp = (node)s1.Pop(); 
            s2.Push(temp); 
  
            // Push left and right children of 
            // removed item to s1 
            if (temp.left != null) 
                s1.Push(temp.left); 
            if (temp.right != null) 
                s1.Push(temp.right); 
        } 
  
        // Print all elements of second stack 
        while (s2.Count > 0) { 
            node temp = (node)s2.Pop(); 
            Console.Write(temp.data + " "); 
        } 
    } 
  
    public static void Main(String[] args) 
    { 
        // Let us construct the tree 
        // shown in above figure 
  
        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); 
  
        postOrderIterative(root); 
    } 
} 
  
// This code is contributed by Arnab Kundu 

Javascript

<script> 
  
      // JavaScript program for iterative post 
      // order using two stacks 
      class node { 
        constructor(data) { 
          this.data = data; 
          this.left = null; 
          this.right = null; 
        } 
      } 
  
      function postOrderIterative(root) { 
        // Two stacks as used in explanation 
        // Create two stacks 
        var s1 = []; 
        var s2 = []; 
  
        if (root == null) return; 
  
        // Push root to first stack 
        s1.push(root); 
  
        // Run while first stack is not empty 
        while (s1.length > 0) { 
          // Pop an item from s1 and Push it to s2 
          var temp = s1.pop(); 
          s2.push(temp); 
  
          // Push left and right children of 
          // removed item to s1 
          if (temp.left != null) s1.push(temp.left); 
          if (temp.right != null) s1.push(temp.right); 
        } 
  
        // Print all elements of second stack 
        while (s2.length > 0) { 
          var temp = s2.pop(); 
          document.write(temp.data + " "); 
        } 
      } 
  
      // Let us construct the tree 
      // shown in above figure 
  
      var 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); 
  
      postOrderIterative(root); 
        
</script>

Output:

4 5 2 6 7 3 1

Time complexity: O(n) where n is no of nodes in a binary tree

Auxiliary space: O(n) because using stack s1 and s2

Following is an overview of the above post.
Iterative preorder traversal can be easily implemented using two stacks. The first stack is used to get the reverse postorder traversal. The steps to get a reverse postorder are similar to iterative preorder.
You may also like to see a method which uses only one stack.
This article is compiled by Aashish Barnwal.

GeeksforGeeks

Improve

Previous Article

Iterative Preorder Traversal

Diagonal Traversal of Binary Tree

Similar Reads

Iterative Postorder Traversal | Set 2 (Using One Stack)

We have discussed a simple iterative postorder traversal using two stacks in the previous post. In this post, an approach with only one stack is discussed. The idea is to move down to leftmost node using left pointer. While moving down, push root and root's right child to stack. Once we reach leftmost node, print it if it doesn't have a right child

Iterative Postorder traversal | Set 3

We have seen different ways of performing postorder traversal on Binary Trees. Post Order Traversal.Iterative Postorder Traversal using Two Stacks.Iterative Postorder Traversal using One Stack. Here is another way of performing the postorder traversal on a Binary Tree iteratively using a single stack.Consider the Below Terminologies: 0 - Left eleme

Iterative Postorder Traversal of N-ary Tree

Given an N-ary tree, the task is to find the post-order traversal of the given tree iteratively.Examples: Input: 1 / | \ 3 2 4 / \ 5 6 Output: [5, 6, 3, 2, 4, 1] Input: 1 / \ 2 3 Output: [2, 3, 1] Approach:We have already discussed iterative post-order traversal of binary tree using one stack. We will extend that approach for the n-ary tree. The id

Find postorder traversal of BST from preorder traversal

Given an array representing preorder traversal of BST, print its postorder traversal. Examples: Input : 40 30 35 80 100 Output : 35 30 100 80 40 Input : 40 30 32 35 80 90 100 120 Output : 35 32 30 120 100 90 80 40 Prerequisite: Construct BST from given preorder traversal Simple Approach: A simple solution is to first construct BST from a given preo

Construct a BST from given postorder traversal using Stack

Given postorder traversal of a binary search tree, construct the BST.For example, If the given traversal is {1, 7, 5, 50, 40, 10}, then following tree should be constructed and root of the tree should be returned. 10 / \ 5 40 / \ \ 1 7 50 Input : 1 7 5 50 40 10 Output : Inorder traversal of the constructed tree: 1 5 7 10 40 50 If the given traversa

Preorder, Postorder and Inorder Traversal of a Binary Tree using a single Stack

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-order, and In-order iteratively using only one stack traversal. Examples: Input: Output:Preorder Traversal: 1 2 3Inorder Traversal: 2 1 3Postorder Traversal: 2 3 1 Input: Output:Preorder traversal: 1 2 4 5 3 6 7Inorder traversal: 4 2 5 1 6 3 7Post-order tr

Postorder traversal of Binary Tree without recursion and without stack

Given a binary tree, perform postorder traversal. Prerequisite - Inorder/preorder/postorder traversal of tree We have discussed the below methods for postorder traversal. 1) Recursive Postorder Traversal. 2) Postorder traversal using Stack. 2) Postorder traversal using two Stacks. Approach 1 The approach used is based on using an unordered set to k

Find n-th node in Postorder traversal of a Binary Tree

Given a Binary tree and a number N, write a program to find the N-th node in the Postorder traversal of the given Binary tree. Prerequisite: Tree Traversal Examples: Input : N = 4 11 / \ 21 31 / \ 41 51 Output : 31 Explanation: Postorder Traversal of given Binary Tree is 41 51 21 31 11, so 4th node will be 31. Input : N = 5 25 / \ 20 30 / \ / \ 18

Construct a Complete N-ary Tree from given Postorder Traversal

Given an array arr[] of size M that contains the post-order traversal of a complete N-ary tree, the task is to generate the N-ary tree and print its preorder traversal. A complete tree is a tree where all the levels of the tree are completely filled, except may be for the last level but the nodes in the last level are as left as possible. Examples:

Find parent of given node in a Binary Tree with given postorder traversal

Given two integers N and K where N denotes the height of a binary tree, the task is to find the parent of the node with value K in a binary tree whose postorder traversal is first [Tex]2^{N}-1 [/Tex] natural numbers [Tex](1, 2, ... 2^{N}-1) [/Tex] For N = 3, the Tree will be - 7 / \ 3 6 / \ / \ 1 2 4 5 Examples: Input: N = 4, K = 5 Output: 6 Explan

Article Tags :

Practice Tags :