What is Depth First Search?

Hugo — Fri, 14 Apr 2023 15:44:26 +0000

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:

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

The Three types of Searching Orders

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

Pre-Order
In-Order
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

What is Dynamic Programming?

Hugo — Fri, 24 Mar 2023 00:49:02 +0000

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming.
The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later.

This simple optimization reduces time complexities from exponential to linear.

For example, if we write a simple recursive solution for Fibonacci, we get exponential time complexity and if we optimize it by storing solutions of sub-problems, time complexity reduces to linear.

If you're not familiar with Big O Notation, I'll be writing a post eventually. But simply put, Big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

In other words:

Dynamic Programming is simply an optimization technique using Cache, to store previously calculated values and return these values whenever they're needed, without having to re-calculate them again.
We save these values in Cache (usually called memo), using an Hashmap data structure, for fast access.

Types of Dynamic Programming

It's important to note that there's two approaches to dynamic programming. Memoization and Tabulation.

One of the most used examples when introducing Dynamic Programming and recursion is the Fibonnaci sequence.

Take a look at the image below:

In this image we're calculating the Fibonnaci of 5.
The highlighted values represent repeated calculations, which we can store in cache whenever when we calculate them for the first time, this will ensure we not re-calculate them again, whenever these values are needed.

This is a simple example. However, to give you a broader view of the great improvement of Dynamic Programming, imagine we needed to calculate the Fibonnaci of 30, here's how many calculations we would do:

Without DP: 2692537 calculations.
With DP: 59 calculations.

A pretty mind-blowing difference, don't you think?

Let's see how we can implement DP by improving the recursive Fibonnaci solution.

Recursive Fibbonaci

function fib(n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n-1) + fib(n-2)
    }
}
// Time Complexity - O(2^n)

Fibbonaci with Memoization

function dynamicFib(n, cache) {
    let cache = cache || {};
    if(cache[n]) return cache[n]

    // base case
    if (n < 2) return n;

    return cache[n] = dynamicFib(n-1, cache[n]) + dynamicFib(n-2, cache[n])
}
// Time Complexity - O(n)

To practice your new gained knowledge, I encourage you to try solving the following leetcode problem: Climbing Stairs

DEV Community: Hugo

What is Depth First Search?