Postorder Tree Traversal Without Recursion in C++

January 24, 2021

Postorder Tree Travesal Without Recursion

There are three types of traversals in trees:Preorder,Inorder and Postorder. The traversals can be performed using recursion or stack.In this article, postorder traversal is performed using two stacks. The Last In First Out principle of stack is used to get postorder sequence.

Postorder Tree Traversal without recursion in C++

More About Postorder Traversal:

  1. Postorder traversal is a depth first algorithm.
  2. In postorder traversal, we first move to the left subtree then to the right subtree and finally print the node.
  3. Post order traversal is used when we want to free the nodes of the tree.
  4. It is also used to find the postfix expression.

Algorithm:

  1. Create two stacks: s1 and s2.
  2. Push the root in s1.
  3. Continue until s1 is empty.
  4. Pop the top element of s1 and push it into s2.
  5. Push the left and the right child of top element to s1.
  6. Print the s2 stack when s1 is empty.
Working of how to create a tree using preorder traversal in c++

Code:

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void postorder(Tree *root) {
    // If empty return;
    if (root == NULL) return;
    stack <Tree *> s1,s2;
    Tree * temp = root;
    s1.push(temp);
    // Continue till stack is empty 
    while (!s1.empty()) {
        temp = s1.top();
        s1.pop();
        // Push the top element of first stack
        s2.push(temp);
        // Push the left child of the top element
        if (temp -> left != NULL) s1.push(temp -> left);
        // Push the right child of the top element
        if (temp -> right != NULL) s1.push(temp -> right);
    }
    // Print the second stack
    while(!s2.empty()) {
        cout << s2.top() -> data << ” “;
        s2.pop();
    }
    cout << endl;
}
int main() {
    Tree *root = new Tree(10);
    root -> left = new Tree(20);
    root -> right = new Tree(30);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(50);
    cout << “Postorder Traversal” << endl;
    postorder(root); 
    return 0;
}

Output:

Postorder Traversal
40 50 20 30 10

 

Time Complexity Of Postorder Traversal without Recursion

Time Complexity

O(n)

Space Complexity

O(n)