1. Overview
In this tutorial, we’ll explore the Depth-first search in Java.
Depth-first search (DFS) is a traversal algorithm used for both Tree and Graph data structures. The depth-first search goes deep in each branch before moving to explore another branch.
In the next sections, we’ll first have a look at the implementation for a Tree and then a Graph.
To see how to implement these structures in Java, have a look at our previous tutorials on Binary Tree and Graph.
2. Tree Depth-first Search
There are three different orders for traversing a tree using DFS:
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
2.1. Preorder Traversal
In preorder traversal, we traverse the root first, then the left and right subtrees.
We can simply implement preorder traversal using recursion:
- Visit current node
- Traverse left subtree
- Traverse right subtree
public void traversePreOrder(Node node) {
if (node != null) {
visit(node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}
We can also implement preorder traversal without recursion.
To implement an iterative preorder traversal, we’ll need a Stack, and we’ll go through these steps:
- Push root in our stack
- While stack is not empty
- Pop current node
- Visit current node
- Push right child, then left child to stack
public void traversePreOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node current = root;
stack.push(root);
while(!stack.isEmpty()) {
current = stack.pop();
visit(current.value);
if(current.right != null) {
stack.push(current.right);
}
if(current.left != null) {
stack.push(current.left);
}
}
}
2.2. Inorder Traversal
For inorder traversal, we traverse the left subtree first, then the root, then finally the right subtree.
Inorder traversal for a binary search tree means traversing the nodes in increasing order of their values.
We can simply implement inorder traversal using recursion:
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
visit(node.value);
traverseInOrder(node.right);
}
}
We can also implement inorder traversal without recursion, too:
- Initialize current node with root
- While current is not null or stack is not empty
- Keep pushing left child onto stack, till we reach current node’s left-most child
- Pop and visit the left-most node from stack
- Set current to the right child of the popped node
public void traverseInOrderWithoutRecursion() {
Stack stack = new Stack<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
Node top = stack.pop();
visit(top.value);
current = top.right;
}
}
2.3. Postorder Traversal
Finally, in postorder traversal, we traverse the left and right subtree before we traverse the root.
We can follow our previous recursive solution:
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
visit(node.value);
}
}
Or, we can also implement postorder traversal without recursion:
- Push root node in s**tack
- While stack is not empty
- Check if we already traversed left and right subtree
- If not then push right child and left child onto stack
public void traversePostOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node prev = root;
Node current = root;
stack.push(root);
while (!stack.isEmpty()) {
current = stack.peek();
boolean hasChild = (current.left != null || current.right != null);
boolean isPrevLastChild = (prev == current.right ||
(prev == current.left && current.right == null));
if (!hasChild || isPrevLastChild) {
current = stack.pop();
visit(current.value);
prev = current;
} else {
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
}
3. Graph Depth-first Search
The main difference between graphs and trees is that graphs may contain cycles.
So to avoid searching in cycles, we will mark each node when we visit it.
We’ll see two implementations for graph DFS, with recursion, and without recursion.
3.1. Graph DFS with Recursion
First, let’s start simple with recursion:
- We’ll start from a given node
- Mark current node as visited
- Visit current node
- Traverse unvisited adjacent vertices
public boolean[] dfs(int start) {
boolean[] isVisited = new boolean[adjVertices.size()];
return dfsRecursive(start, isVisited);
}
private boolean[] dfsRecursive(int current, boolean[] isVisited) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
dfsRecursive(dest, isVisited);
}
return isVisited;
}
3.2. Graph DFS Without Recursion
We can also implement graph DFS without recursion. We’ll simply use a Stack:
- We’ll start from a given node
- Push start node into stack
- While Stack not empty
- Mark current node as visited
- Visit current node
- Push unvisited adjacent vertices
public void dfsWithoutRecursion(int start) {
Stack<Integer> stack = new Stack<Integer>();
boolean[] isVisited = new boolean[adjVertices.size()];
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.pop();
if(!isVisited[current]){
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
stack.push(dest);
}
}
return isVisited;
}
3.4. Topological Sort
There are a lot of applications for graph depth-first search. One of the famous applications for DFS is Topological Sort.
Topological Sort for a directed graph is a linear ordering of its vertices so that for every edge the source node comes before the destination.
To get topologically sorted, we’ll need a simple addition to the DFS we just implemented:
- We need to keep the visited vertices in a stack because the topological sort is the visited vertices in a reversed order
- We push the visited node to the stack only after traversing all its neighbors
public List<Integer> topologicalSort(int start) {
LinkedList<Integer> result = new LinkedList<Integer>();
boolean[] isVisited = new boolean[adjVertices.size()];
topologicalSortRecursive(start, isVisited, result);
return result;
}
private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList<Integer> result) {
isVisited[current] = true;
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
topologicalSortRecursive(dest, isVisited, result);
}
result.addFirst(current);
}
4. Conclusion
In this article, we discussed the depth-first search for both the Tree and Graph data structures.
The full source code is available on GitHub.