What is Depth First Search?

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

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.

ROOT-LEFT-RIGHT

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.

LEFT-ROOT-RIGHT

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.

LEFT-RIGHT-ROOT

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