Preorder Traversal in Binary Tree in Java
Preorder Traversal in Binary Tree
Preorder Traversal in Binary Tree in Java is a fundamental tree traversal technique where nodes are visited in a specific order:
Root → Left → RightIt is a Depth First Traversal (DFS) method and is widely used in problems like tree copying, serialization, and expression tree evaluation.
What is Preorder Traversal?
In preorder traversal, we:
- Visit the root node
- Traverse the left subtree
- Traverse the right subtree
Steps to Find Preorder Traversal in Binary Tree
Here are some of the steps for tree traversal :
- Step 1: First we will print the root element which is 10 in above example.
- Step 2: Traverse the left subtree recursively. The only node on left subtree is 20 . So print it and move to the right subtree of root.
- Step 3: 30 is the root of right sub-tree , therefore , print it and move to its left.
- Step 5: Print 40 which is the only element in left subtree and move to right of it’s parent.
- Step 6: Print 50 which is the last element of the tree.
- Step 7 : Therefore, the printing sequence will be 10,20,30,40,50.
Example of Preorder Traversal:
Methods for Preorder Traversal in Binary Tree in Java
Preorder traversal in Binary tree can be performed using 2 methods using Java:
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Methods for Preorder Traversal in Binary Tree
Method 1: Recursive Preorder Traversal
Algorithm for Preorder Traversal
preorder(node)
1. If node is null
return
2. Print node.data
3. Call preorder(node.left)
4. Call preorder(node.right)
Java Code:
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PreorderTraversal {
Node root;
void preorder(Node node) {
if (node == null)
return;
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
}
public static void main(String[] args) {
PreorderTraversal tree = new PreorderTraversal();
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(tree.root);
}
}
Output:
Preorder Traversal: 10 20 40 50 30
Method for Preorder Traversal in Binary Tree
Method 2: Iterative Preorder Traversal (Using Stack)
Algorithm for Iterative Preorder Traversal
Instead of recursion, we use a stack to simulate traversal.
Key idea:
- Push root
- Process node
- Push right child first, then left (so left is processed first)
1. Create an empty stack
2. Push root node
3. While stack is not empty:
a. Pop node
b. Print node
c. Push right child (if exists)
d. Push left child (if exists)
Java Code:
import java.util.Stack;
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PreorderIterative {
Node root;
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) {
PreorderIterative tree = new PreorderIterative();
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();
}
}
Output:
Preorder Traversal: 10 20 40 50 30
Space Complexity: O(h)
where, h = height of the binary tree
Skewed Tree → O(n)
To wrapping up with
Preorder Traversal in Binary Tree in Java:
If root is null → no output
Always check null before accessing nodes
Stack should not be empty before pop
Common Problem with Preorder traversal:
Forgetting traversal order (Root → Left → Right)
Pushing left before right in stack (wrong order)
Missing null checks
Confusing with inorder traversal
Frequently Asked Questions
Answer:
It is a traversal where nodes are visited in Root → Left → Right order.
Answer:
Time complexity is O(n) because every node is visited once.
Answer:
Yes, using a stack (iterative method).
Answer:
It is used for tree copying, serialization, and prefix expressions.
Answer:
Space complexity is O(h), where h is the height of the tree.
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