Postorder Tree Traversal Without Recursion in C++
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.
More About Postorder Traversal:
- Postorder traversal is a depth first algorithm.
- In postorder traversal, we first move to the left subtree then to the right subtree and finally print the node.
- Post order traversal is used when we want to free the nodes of the tree.
- It is also used to find the postfix expression.
Algorithm:
- Create two stacks: s1 and s2.
- Push the root in s1.
- Continue until s1 is empty.
- Pop the top element of s1 and push it into s2.
- Push the left and the right child of top element to s1.
- Print the s2 stack when s1 is empty.
Code Implementation for Postorder Tree traversal without recursion
Run
#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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment