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

**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.

res – REST with Spring (eBook) (everywhere)