What is Depth First Search?
Tags: algorithms, programming, leetcode, computerscience
Published: 2023-04-14 15:44:26

## What is Depth First Search?

Depth-First Search (DFS), is a graph/tree traversal algorithm that explores as far as possible along each branch, before backtracking.

This algorithm keeps track of the visited nodes to avoid revisiting them and uses a stack to remember the nodes that still need to be explored.


> We can implement DFS **recursively** or **iteratively**. 

It's important to note however, that in the Recursive implementation, the **function call stack** is used as a stack data structure, while in the iterative implementation, an explicit stack is used instead.

#### Why is this used?

DFS is commonly used to solve problems involving graphs and trees, such as finding connected components, detecting cycles, and traversing a tree in a specific order.

> _Cool Fact: A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux, as a strategy for solving mazes. You can read more about it [here](https://en.wikipedia.org/wiki/Maze-solving_algorithm)_

#### When should you use DFS:

1. If solutions are frequent and located deep in the tree.
2. Determining whether a path exists between two nodes.
3. If the tree is very wide.

---

## The Three types of Searching Orders

There's 3 types of Traversal methods in DFS, these are:

1. Pre-Order
2. In-Order
3. Post-Order


### Pre-Order Traversal

Pre-order traversal is to visit the root first. Then traverse the left subtree. And finally, traverse the right subtree.
> <mark>ROOT-LEFT-RIGHT</mark>


![Tree data structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9zbbml8wxsycww8xbogk.png)

**Output**: F-B-A-D-C-E-G-I-H 

---

### In-Order Traversal

In Order is to traverse the left subtree first. Then visit the Root node. And finally, traverse the right subtree.
And typically, for binary search tree, we can retrieve all the data in **sorted** order using this type of traversal.

> <mark>LEFT-ROOT-RIGHT</mark>


![Tree data structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9zbbml8wxsycww8xbogk.png)

Output: A-B-C-D-E-F-G-H-I

---


### Post-Order Traversal

In Order is to traverse the left subtree first. Then traverse the right subtree. And then we visit the root.


> <mark>LEFT-RIGHT-ROOT</mark>


![Tree data structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9zbbml8wxsycww8xbogk.png)

Output: A-C-E-D-B-H-I-G-F

---

Here's how to implement each traversal method in code:

> Please note that I'm using normal Recursion here. Tail Recursion however, would be more efficient. 

#### Pre-Order:

```
function preorderTraversal(root) {
	if (!root) return [];
	let result = [];

	result.push(root.val);
	
	if (root.left) {
		result = [...result, ...preorderTraversal(root.left)]
	}
	if (root.right) {
		result = [...result, ...preorderTraversal(root.right)]
	}

	return result;
}
```

#### In-Order:

```
function preorderTraversal(root) {
	if (!root) return [];
	let result = [];

	if (root.left) {
		result = [...result, ...preorderTraversal(root.left)]
	}
	
	result.push(root.val);
	
	if (root.right) {
		result = [...result, ...preorderTraversal(root.right)]
	}

	return result;
}

```

#### Post-Order:

```
function preorderTraversal(root) {
	if (!root) return [];
	let result = [];

	if (root.left) {
		result = [...result, ...preorderTraversal(root.left)]
	}
	
	if (root.right) {
		result = [...result, ...preorderTraversal(root.right)]
	}
	
	result.push(root.val);
	return result;
}
```
---
I try to make these "hard" concepts a bit more easy to understand. Please let me know your thoughts and if you would like to see more of these! 😄

- Hugo