Given a binary tree, write a program to perform an iterative postorder traversal and print the values of the nodes as they are visited.
In a postorder traversal, we visit the left subtree, then the right subtree, and finally the root node.
Consider the following binary tree:
1
/ \
2 3
/ \
4 5
Expected Output:
The expected output for the iterative postorder traversal of the given binary tree is: 2 4 5 3 1.
Table of Contents
Iterative Post-order Traversal C++ Solution:
#include <iostream>
#include <stack>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// Function to perform iterative postorder traversal
void iterativePostOrderTraversal(TreeNode* root) {
if (!root)
return;
stack<TreeNode*> st;
st.push(root);
stack<int> result; // To store the postorder traversal result
while (!st.empty()) {
TreeNode* current = st.top();
st.pop();
result.push(current->val);
// Push left and right subtrees (right first to ensure left subtree is processed first)
if (current->left)
st.push(current->left);
if (current->right)
st.push(current->right);
}
// Print the postorder traversal result
cout << "Iterative Postorder Traversal: ";
while (!result.empty()) {
cout << result.top() << " ";
result.pop();
}
cout << endl;
}
int main() {
// Create the binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(5);
// Perform iterative postorder traversal
iterativePostOrderTraversal(root);
return 0;
}
Time and Space Complexity:
The time complexity of the iterative postorder traversal is O(n), where n is the number of nodes in the binary tree, since we visit each node once.
The space complexity is O(h), where h is the height of the binary tree.
In the worst case (skewed tree), the space complexity could be O(n), and in the best case (balanced tree), it could be O(log n).
Code Explanation:
In this program, the iterativePostOrderTraversal function performs the iterative postorder traversal using two stacks. The main stack (st) is used to simulate the traversal, and the result stack is used to store the postorder traversal result. It starts by pushing the root node onto the main stack and then enters a loop where it pops nodes from the main stack, pushes their values onto the result stack, and pushes their left and right subtrees onto the main stack.
After the traversal, the program prints the postorder traversal result by popping elements from the result stack.