Tree Traversal : Depth First Search (DFS)
Tree Traversal : Depth First Search in Java
Depth First Search in Java is a fundamental tree traversal technique where we explore as deep as possible along one branch before backtracking. It is widely used in recursion based problems and forms the basis of many advanced algorithms.
This guide explains DFS in a simple and structured way, including types of DFS, approach, algorithms, Java implementation, examples, and best practices.
Tree Traversal: Depth First Search
DFS is a traversal technique where:
- We go deep into the tree first
- Then backtrack to explore other branches
Unlike BFS (level order), DFS explores depth before breadth.
Example Tree:
1
/ \
2 3
/ \ \
4 5 6DFS Traversals:
Preorder: 1 → 2 → 4 → 5 → 3 → 6
Inorder: 4 → 2 → 5 → 1 → 3 → 6
Postorder: 4 → 5 → 2 → 6 → 3 → 1
Steps for Depth First Search Tree Treaversal
Before practicing Depth First Search in Java, we will go through Step by step process for performing DFS alongwith comprehensive Algorithm explanation:
- Step 1: Start from the root node i.e. 50 and print it.
- Step 2: Move to the left child of 50, which is 30, and print it.
- Step 3: Move to the left child of 30, which is 10, and print it.
- Step 4: Now, 10 has no children, so backtrack to node 30.
- Step 5: Move to the right child of 30, which is 40, and print it.
- Step 6: 40 has no children, so backtrack to root node 50.
- Step 7: Move to the right child of 50, which is 70, and print it.
- Step 8: Move to the left child of 70, which is 60, and print it.
- Step 9: 60 has no children, so backtrack to node 70.
- Step 10: Move to the right child of 70, which is 90, and print it.
Final Output Sequence: 50 30 10 40 70 60 90
Algorithm for Depth First Search in Java
Algorithm for performing Depth First Search in Java programming:
If the current node is null, return
Process the current node (print or store value)
Recursively traverse the left subtree
Recursively traverse the right subtree
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 Search (DFS)
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
public class DFSExample {
// Preorder Traversal
public static void preorder(Node root) {
if (root == null) return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Inorder Traversal
public static void inorder(Node root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// Postorder Traversal
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);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);
System.out.print("Preorder: ");
preorder(root);
System.out.print("\nInorder: ");
inorder(root);
System.out.print("\nPostorder: ");
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
Space Complexity: O(h), h = height of tree
Worst case: O(n), Best case: O(log n)
Common Insights on Depth First Search in Java
Types of DFS Traversals
DFS in trees is mainly of three types:
1. Preorder Traversal (Root → Left → Right)
Visit root first, then left subtree, then right subtree
2. Inorder Traversal (Left → Root → Right)
Visit left subtree, then root, then right subtree
3. Postorder Traversal (Left → Right → Root)
Visit left subtree, then right subtree, then root
DFS is naturally implemented using recursion and Inorder traversal of BST gives sorted order. Postorder is useful for deletion of trees and Preorder is useful for copying trees.
Best Practices:
Always check for null nodes
Use recursion carefully for deep trees
Use iterative DFS if recursion depth is high
Keep traversal functions clean and simple
Understand differences between traversal types
Frequently Asked Questions
Answer:
DFS is a method of exploring nodes deeply before moving to other branches.
Answer:
Preorder, Inorder, and Postorder traversal.
Answer:
O(n), since all nodes are visited once.
Answer:
Use DFS when exploring paths, recursion problems, or tree-based computations.
Answer:
DFS goes deep first (stack/recursion), while BFS goes level by level (queue).
Login/Signup to comment