**Get started with Spring 5 and Spring Boot 2, through the ***Learn Spring* course:

*Learn Spring*course:

**>> CHECK OUT THE COURSE**

Last modified: September 22, 2020

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.

There are three different orders for traversing a tree using DFS:

- Preorder Traversal
- Inorder Traversal
- Postorder 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 s*tack* - While
*stack*is not empty- Pop
*current*node - Visit
*current*node - Push
*right*child, then*left*child to*stack*

- Pop

```
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);
}
}
}
```

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:

- Push
*root*node to*s**tack* - While s
*tack*is not empty- Keep pushing
*left*child onto*stack,*till we reach*current*node's left-most child - Visit
*current*node - Push
*right*child onto*stack*

- Keep pushing

```
public void traverseInOrderWithoutRecursion() {
Stack<Node> stack = new Stack<Node>();
Node current = root;
stack.push(root);
while(! stack.isEmpty()) {
while(current.left != null) {
current = current.left;
stack.push(current);
}
current = stack.pop();
visit(current.value);
if(current.right != null) {
current = current.right;
stack.push(current);
}
}
}
```

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 s
*tack*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);
}
}
}
}
```

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.

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 void dfs(int start) {
boolean[] isVisited = new boolean[adjVertices.size()];
dfsRecursive(start, isVisited);
}
private void dfsRecursive(int current, boolean[] isVisited) {
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
dfsRecursive(dest, isVisited);
}
}
```

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

- Mark

```
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();
isVisited[current] = true;
visit(current);
for (int dest : adjVertices.get(current)) {
if (!isVisited[dest])
stack.push(dest);
}
}
}
```

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);
}
```

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.