Depth First Traversal in Java
Depth First Traversal
In this article, we will understand Depth First Traversal in Java, including its types, approach, algorithm, implementation, examples, and best practices.
Depth First Traversal (DFT), commonly referred to as Depth First Search (DFS) in trees, is a technique where we explore a tree as deep as possible before backtracking. It is one of the most fundamental traversal methods used in tree based problems.
What is Depth First Traversal?
Depth First Traversal means:
- Visit a node
- Go deep into one subtree
- Backtrack and explore other branches
Unlike level order traversal (BFS), DFS focuses on depth rather than breadth.
Types of Depth First Traversal in Java
1. Preorder Traversal (Root → Left → Right)
- Visit root first
- Then traverse left subtree
- Then traverse right subtree
2. Inorder Traversal (Left → Root → Right)
- Traverse left subtree
- Visit root
- Traverse right subtree
3. Postorder Traversal (Left → Right → Root)
- Traverse left subtree
- Traverse right subtree
- Visit root
Example:
Why Do We Use Depth First Traversal?
DFS is useful for:
- Tree traversals
- Recursive problem solving
- Path based problems
- Expression trees
- Backtracking algorithms
Algorithm for Depth First Traversal
Steps:
- If node is null, return
- Process (print) the node
- Traverse left subtree
- Traverse right subtree
Pseudocode:
Preorder(node):
if node == null:
return
process(node)
Preorder(node.left)
Preorder(node.right)Steps:
- If node is null, return
- Traverse left subtree
- Process the node
- Traverse right subtree
Pseudocode:
Inorder(node):
if node == null:
return
Inorder(node.left)
process(node)
Inorder(node.right)Steps:
- If node is null, return
- Traverse left subtree
- Traverse right subtree
- Process the node
Pseudocode:
Postorder(node):
if node == null:
return
Postorder(node.left)
Postorder(node.right)
process(node)Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Java Code for Depth First Traversal
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PreorderTraversal {
public static void preorder(Node root) {
if (root == null) return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
System.out.print("Preorder: ");
preorder(root);
}
}
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class InorderTraversal {
public static void inorder(Node root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
System.out.print("Inorder: ");
inorder(root);
}
}
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class PostorderTraversal {
public static void postorder(Node root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.data + " ");
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
System.out.print("Postorder: ");
postorder(root);
}
}
Input:
1
/ \
2 3
/ \ \
4 5 6
Output:
Preorder: 1 2 4 5 3 6 Inorder: 4 2 5 1 3 6 Postorder: 4 5 2 6 3 1
Worst Case (Skewed Tree): O(n)
Reason:
- Depends on recursion stack depth (height of tree)
- Height = h
- Space = O(h)
Conclusion….
Common Insights:
- DFS is naturally recursive
- Inorder traversal gives sorted order in BST
- Postorder is useful for deletion
- Preorder is used for tree copying
Best Practices:
- Always handle null nodes
- Use recursion carefully for deep trees
- Use iterative approach for large trees
- Keep traversal functions simple
- Understand differences between traversal types
Frequently Asked Questions
Answer:
Depth First Traversal in Java is a method of visiting all nodes in a tree by exploring as deep as possible before backtracking.
Answer:
The three types are Preorder, Inorder, and Postorder traversal.
Answer:
The time complexity is O(n) since each node is visited once.
Answer:
It is used in tree traversal, recursion problems, path finding, and backtracking algorithms.
Answer:
DFS explores depth using recursion/stack, while BFS explores level by level using a queue.
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
