Exploring DFS & BFS Through Visuals

Jan 09, 2024

Intro

Depth-First Search (DFS) and Breadth-First Search (BFS) are the most common coding interview algorithms that you need to know.

In many coding problems, you’re required to traverse over each item in a Tree or Graph in order to perform some operations. This is where you need to use DFS or BFS.

These algorithms can seem a bit complex at first, especially if you're just starting out. But they can actually be quite simple to understand, especially when you approach them visually.

In today's article, we will learn them with visualizations in a way that's easy to understand, even if you're a beginner.

Depth-First Search (DFS)

DFS is a more common algorithm in coding interviews than BFS. It explores as far as possible along each branch before backtracking.

Let’s say we have a binary search tree of these elements.

With DFS we

Start at the root (57).
Go to the left subtree of 57, which is the subtree rooted at 28.
In the subtree rooted at 28, go to its left subtree, i.e., node 9.
Go to the left subtree of 9, which is 2
Node 2 has no left subtree, so process node 2.
Back to the root of this subtree, i.e., process node 9.
Go to the right subtree of 9, i.e., node 26, and process node 26.

Repeat the process for all the left and right subtrees.

And we have 3 types of DFS algorithms

Inorder

The one that we just saw is the inorder algorithm, where we visit the left subtree, then the root, then the right subtree. Inorder traversal retrieves elements in sorted order.

function inorderTraversal(root) {
    if (root === null) {
        return;
    }
    inorderTraversal(root.left);
    console.log(root.val); // process the node
    inorderTraversal(root.right);
}

Preorder

The preorder algorithm visits the root first, then the left subtree, then the right subtree. For example, it can be used to create a copy of the tree.

function preorderTraversal(root) {
    if (root === null) {
        return;
    }
    console.log(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

Postorder

Postorder visits the left subtree, the right subtree, and then the root. A use case of this is deleting the tree, as you delete subtrees first, then the root.

function postorderTraversal(root) {
    if (root === null) {
        return;
    }
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    console.log(root.val);
}

To visualize the difference between Inorder, Preorder, and Postorder algorithms, just visualize that each node has a flag attached to it, and you need to traverse in a way to collect all the flags.

In the case of Preorder, the flag is attached to the left; for Inorder, it’s at the bottom; and for Postorder, it’s on the left.

In terms of common usage, Inorder is often used in Binary Search Trees because it retrieves elements in sorted order.

Time and Space Complexities of DFS

Time Complexity: O(n), where n is the number of nodes. Each node is visited once.
Space Complexity: O(h), where h is the tree's height. This is due to the recursion stack.

Common Use Cases of DFS

Building a BST from a sorted array and vice versa: With DFS, if the tree is a Binary search tree, we can loop with an inorder algorithm and push the items into the array — so we will have the items in sorted order in our array. The opposite is also possible; we can loop through an array of sorted elements and build a BST.
Checking if a tree is a BST: This is also done with inorder traversal; we just loop through the tree elements and check that each node value is greater than its left item and smaller than its right item.
Path Finding: DFS explores paths in a graph or tree, making it useful for finding a path between two nodes.
Backtracking Algorithms: DFS is often used in backtracking algorithms for combinatorial problems, such as permutations and combinations, sudoku solvers, etc.

The downside of DFS is that it can get slow if the tree is unbalanced

Breadth-First Search (BFS)

Another type of traversal algorithm is BFS, which visits nodes level by level from the root downwards.

Imagine a BST with these nodes.

With BFS we

Start at the root (5) and add it to the queue.
Process node from the front of the queue:
Process node 5. Add its children (3 and 8) to the queue.
Process node 3. Add its children (1 and 4) to the queue.
Process node 8. Add its child (9) to the queue.
Process node 1. It has no children.
Process node 4. It has no children.
Process node 9. It has no children.

BFS Traversal Result: 5, 3, 8, 1, 4, 9

The code of BFS is usually written in iterative form, as recursion doesn’t suit well with this algorithm. Because it needs to remember where to go next after processing each layer, we need to keep the order in a queue data structure to track nodes.

function bfs(root) {
    if (root === null) {
        return;
    }
    let queue = [root];

    while (queue.length > 0) {
        let node = queue.shift();
        console.log(node.val);

        if (node.left !== null) {
            queue.push(node.left);
        }
        if (node.right !== null) {
            queue.push(node.right);
        }
    }
}

Time and Space Complexities of BFS

Time Complexity: You might think that the time complexity is O(n²) because there are 2 nested loops. But despite nested loops, each node is visited only once; therefore, the time complexity is O(n).
Space Complexity: O(n), where n is the maximum width of the tree.

Common use cases of BFS

Level Order Traversal in Trees: BFS is the go-to algorithm for traversing a tree or graph level by level. It’s often used to print all tree nodes at each depth level.
Shortest Path: BFS is ideal for finding the shortest path, as it explores all neighbors at the present depth before moving on to the nodes at the next depth level. For example, in Social Networking Applications, BFS can be used to find people within a certain distance (or “degrees of separation”) from a user, reflecting the “friends of friends” concept.
Also, in Solving Puzzles and Games, BFS is applied in games or puzzle-solving, such as finding the minimum number of moves to solve a puzzle or to reach a particular state in a game.

The downside is that it requires more memory compared to DFS

Outline and Next Steps

I recommend you practice some LeetCode problems (provided below) to familiarize yourself with DFS and BFS algorithms because they are the most common ones for interviews.

Practice DFS
https://leetcode.com/problems/binary-tree-inorder-traversal/ https://leetcode.com/problems/recover-binary-search-tree/ https://leetcode.com/problems/symmetric-tree/ https://leetcode.com/problems/path-sum/ https://leetcode.com/problems/path-sum-ii/

Practice BFS
https://leetcode.com/problems/same-tree/ https://leetcode.com/problems/binary-tree-level-order-traversal/ https://leetcode.com/problems/binary-tree-level-order-traversal-ii/ https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Also, check out the https://visualgo.net/en/bst, which visualizes these algorithms.

If you’re interested in learning more about the tree data structure on which we usually perform these algorithms, I recommend you check out the most common tree types in coding interviews.

Hayk Simonyan | Substack

Hayk Simonyan