Postorder Tree Traversal without recursion in Java
Postorder Tree Traversal without Recursion
Postorder Tree Traversal without recursion in Java explains how to traverse a binary tree in Left → Right → Root order using an iterative approach (without recursion).
Postorder traversal is the most challenging among all traversals to implement iteratively because the root node is processed after both subtrees. Instead of recursion, we use stack(s) to simulate the traversal.
Postorder Tree Traversal without recursion in Java
What is Postorder Traversal?
In postorder traversal, nodes are visited in the order:
Left → Right → Root
Example Binary Tree
10
/ \
20 30
/ \
40 50
Output
40 50 20 30 10
Why Iterative Postorder is Difficult?
1. Root is processed last.
2. Need to track whether children are already visited.
3. Requires careful stack handling.
2. Need to track whether children are already visited.
3. Requires careful stack handling.
Steps for Postorder Tree Traversal without Recursion
- Step 1: Create two stack as stack1,stack2.
- Step 2: push root which is 5 to stack1. i.e. stack1->5 , stack2->Empty.
- Step 3: pop 5 from stack1 and push it into stack2.Also push right and left child of 5 to stack1. i.e. stack1->7,3 stack2->5.
- Step 4: pop 7 from the stack1 and push it into stack2. Also push left and right child of 7 to stack1. i.e. stack1->8,6,3 and stack2->7,5.
- Step 5: pop 8 from stack1 and push it into stack2. i.e. stack1-> 6,3 and stack2->8,7,5.
- step 6: pop 6 from stack1 and push it into stack2. i.e. stack1->3 and stack2->6,8,7,5.
- step 7: pop 3 from stack1 and push it into stack2 and push left and right child of 3 into stack1. i.e. stack1->4,1 and stack2->3,6,8,7,5.
- step 8: pop 4 from stack1 and push it into stack2.i.e. stack1->1 and stack2->4,3,6,8,7,5.
- step 9: pop 1 from stack1 and push it into stack2. i.e. stack1->Empty and stack2->1,4,3,6,8,7,5.
- step 10: As stack1 is empty so stop and pop all the element from stack2 one by one an print it.
Therefore the sequence will be printed as 1,4,3,6,8,7,5.
Example of Postorder Traversal without Recursion:
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Methods for Postorder Tree Traversal without Recursion
Now we will focus on learning the Methods for Postorder Tree Traversal without Recursion in Java:
- Method 1: Using 2 Stacks
- Method 2: Using 1 Stack
Algorithm for Postorder Tree Traversal without Recursion
Using 2 Stacks
Using 1 Stack
Using 2 Stacks
1. If root is null → return
2. Create two stacks: stack1 and stack2
3. Push root into stack1
4. While stack1 is not empty:
a. Pop node from stack1
b. Push it into stack2
c. Push left child into stack1
d. Push right child into stack1
5. Print elements from stack2
Using 1 Stack
1. Create empty stack
2. Set current = root
3. Initialize lastVisited = null
4. While current != null OR stack not empty:
a. Push left nodes into stack
b. Peek top node
c. If right child exists and not visited:
Move to right child
Else:
Print node
Mark as visited
Java Code for Postorder Tree Traversal without Recursion
Using 2 Stacks
Using 1 Stack
Using 2 Stacks
Run
import java.util.Stack;
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PostorderTwoStacks {
Node root;
void postorder() {
if (root == null)
return;
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
Node current = stack1.pop();
stack2.push(current);
if (current.left != null)
stack1.push(current.left);
if (current.right != null)
stack1.push(current.right);
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().data + " ");
}
}
public static void main(String[] args) {
PostorderTwoStacks tree = new PostorderTwoStacks();
tree.root = new Node(10);
tree.root.left = new Node(20);
tree.root.right = new Node(30);
tree.root.left.left = new Node(40);
tree.root.left.right = new Node(50);
System.out.print("Postorder Traversal: ");
tree.postorder();
}
}
Output
Postorder Traversal: 40 50 20 30 10
Using 1 Stack
Run
import java.util.Stack;
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PostorderOneStack {
Node root;
void postorder() {
Stack stack = new Stack<>();
Node current = root;
Node lastVisited = null;
while (current != null || !stack.isEmpty()) {
// Go to leftmost node
if (current != null) {
stack.push(current);
current = current.left;
} else {
Node peekNode = stack.peek();
// If right child exists and not visited
if (peekNode.right != null &&
lastVisited != peekNode.right) {
current = peekNode.right;
} else {
System.out.print(peekNode.data + " ");
lastVisited = stack.pop();
}
}
}
}
public static void main(String[] args) {
PostorderOneStack tree = new PostorderOneStack();
tree.root = new Node(10);
tree.root.left = new Node(20);
tree.root.right = new Node(30);
tree.root.left.left = new Node(40);
tree.root.left.right = new Node(50);
System.out.print("Postorder Traversal: ");
tree.postorder();
}
}
Output:
Postorder Traversal: 40 50 20 30 10
Time and Space Complexity:
Time Complexity: O(n)
Space Complexity:
For 2 Stacks = O(n)
For 1 Stack = O(h)
Space Complexity:
For 2 Stacks = O(n)
For 1 Stack = O(h)
To wrapping up with
Postorder Traversal in Binary Tree without Recursion in Java:
If root is null → no output
Check stack before pop
Handle leaf nodes correctly
Common Problem with Postorder traversal without recursion:
Incorrect traversal order
Forgetting to track last visited node
Infinite loops in one stack method
Mixing preorder logic
Frequently Asked Questions
Answer:
It is an iterative traversal using stack(s) to process nodes in Left → Right → Root order.
Answer:
Because the root is processed after both subtrees, requiring careful tracking.
Answer:
Time complexity is O(n).
Answer:
Two stacks method is easier to understand and implement.
Answer:
It is O(n) for two stacks and O(h) for one stack.
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
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
Login/Signup to comment