Preorder Tree Traversal without recursion in Java
Preorder Tree Traversal without Recursion
Preorder Tree Traversal without recursion in Java explains how to traverse a binary tree in Root → Left → Right order using an iterative approach (without recursion).
Instead of relying on the system call stack (as in recursion), we explicitly use a stack data structure to control traversal.
Preorder Tree Traversal without Recursion in Java
Why Use Non Recursive Approach?
Recursive Approach:
- Uses system stack
- Less control
- Risk of stack overflow
Iterative Approach:
- Uses explicit stack
- Better control
Steps for Preorder Tree Traversal without Recursion:
- Step 1: Create an empty stack and put the root element into it. i.e Stack-> 6.
- Step 2: Now check if the stack is non- empty. if so , then pop an element from the stack i.e. 6 and print it.
- Step 3: Now check if right child of popped element is not null. If so, then push the element into stack . So stack become , Stack->8.
- Step 4: Similarly check for left child . If so , then push the left child into stack . So stack become , Stack->4,8 .And again goto step 3 and check if stack is not null.
- Step 5: Again pop the top element from stack and print it. i.e print 4.
- Step 6: Check if the right child is not null . If so , then push the right child into stack. i.e push(5) . So stack become , Stack->5,8.
- Step 7: Similarly , check for left child. If it is not null , then push it into stack. i.e. push(2). So our stack become Stack->2,5,8. and again goto step 3 and check if stack is not null.
- Step 8: Again pop an element from the stack and print it. i.e. print 2.Now stack become Stack->5,8.
- Step 9: Now , it’s left and right child is not available hence we again goto step 3.
- Step 10: pop an element from the stack i.e. pop(5) and print it.
- Step 11: Now , As it’s left and right child is not available so move to step 3.
- Step 12: pop an element from the stack i.e. 8 and print it.
- Step 13: Now, check for it’s right child as 9 is it’s right child so put it into the stack. and goto step 3 as there is no left child of element 8.
- Step 14: pop the element from the stack i.e. 9 and print it . Now our stack becomes empty, so stop.
Therefore the sequence will be printed as 6,4,2,5,8,9
Example of Preorder 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
Method for Preorder Traversal without Recursion in Java
Using Stack (Iterative Preorder Traversal)
Visit node first and Push right child first and then Push left child next. This ensures left subtree is processed first.
Algorithm:
1. If root is null
return
2. Create an empty stack
3. Push root into stack
4. While stack is not empty:
a. Pop node from stack
b. Print node.data
c. Push right child (if exists)
d. Push left child (if exists)
Java Code:
import java.util.Stack;
// Node class
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PreorderWithoutRecursion {
Node root;
// Iterative preorder traversal
void preorder() {
if (root == null)
return;
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node current = stack.pop();
System.out.print(current.data + " ");
// Push right first
if (current.right != null)
stack.push(current.right);
// Push left next
if (current.left != null)
stack.push(current.left);
}
}
public static void main(String[] args) {
PreorderWithoutRecursion tree =
new PreorderWithoutRecursion();
// Creating tree
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("Preorder Traversal: ");
tree.preorder();
}
}
Input:
10
/ \
20 30
/ \
40 50 Output:
Preorder Traversal: 10 20 40 50 30
Space Complexity: O(h)
where, h = height of the binary tree
To wrapping up with
Preorder Traversal in Binary Tree without Recursion in Java:
If root is null → no traversal
Always check before popping from stack
Avoid null pointer access
Common Problem with Preorder traversal without recursion:
Pushing left before right (wrong order)
Forgetting to check null root
Incorrect stack operations
Confusing with inorder traversal logic
Frequently Asked Questions
Answer:
It is an iterative method using a stack to traverse a tree in Root → Left → Right order.
Answer:
To avoid recursion overhead and handle large trees efficiently.
Answer:
Time complexity is O(n).
Answer:
Space complexity is O(h), where h is the height of the tree.
Answer:
Yes, using Morris Traversal (advanced method with O(1) space).
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
