I recently discovered this painting and I love it! One of Paul Thek’s paintings

Difference Between DFS vs BFS

If you have read my previous article, this article is for you! After learning about Binary Search Trees, it is time to understand the difference between Depth-First Search (DFS) and Breadth-First Search (BFS). However, the first question that comes to my mind is, is there a difference between a Binary Tree and a Binary Search Tree?

The answer is yes, there is a significant difference between Binary Trees and Binary Search Trees (BSTs). They have different properties and purposes.

Binary Tree

A binary tree is a tree data structure in which each node can have at most two children, typically referred to as the left and right children.

Binary trees have no restrictions on the order of the elements. The left and the right child nodes can be of any value and don’t follow any specific rule for ordering.

They are often used in representing hierarchical data (e.g., file systems), constructing expression trees (used for evaluating arithmetic expressions), and implementing complete binary trees (used for heap-based implementations)

       1
      / \
     2   3
    / \
   4   5

Binary Search Tree(BST)

A binary search tree is a special tree where each node follows a specific ordering, please check here for remembering the rules. BSTs are used in situations where fast search, insertion, and deletion are required. Like implementing dictionaries or symbol tables or managing data that must be kept in sorted order(like priority queues or databases)

       8
      / \
     3  10
    / \   \
   1  6   14
     / \   /
    4  7  13

Every node follows the property that all nodes in the left subtree are less than the root node, and all nodes in the right subtree are greater than the root node.

Ok now we can move on to the difference between DFS vs BFS topic.

Depth-First Search (DFS) and Breadth-First Search (BFS) are fundamental graph traversal algorithms used for exploring nodes and edges in a graph, but they operate in distinctly different ways and are used for different purposes.

DFS

• explores as far as possible along each branch before backtracking
• it uses a stack (either implicitly via recursion or explicitly) to keep track of nodes.

Use cases:

• Path Finding: It is used to find any path from a start node to a target node.
• Cycle Detection: It can be used to detect cycles in a graph.
• Topological Sorting: It is useful for sorting nodes in directed acyclic graphs (DAGs).
• Connectivity Check: It can also be used to determine connected components in a graph.
• Memory Efficient in Sparse Graphs: In graphs that have fewer edges, DFS can be more memory efficient since it doesn’t need to store all nodes on the same level.

BFS

• explores all the neighbors of a node before moving on to the next level of nodes
• it uses a queue to explore nodes layer by layer

Use cases:

• Shortest Path in Unweighted Graphs: It is used to find the shortest path between nodes in unweighted graphs. Since BFS explores level by level, it ensures that you get the shortest distance first.
• Level Order Traversal: In tree-like structures, BFS is often used to traverse nodes level by level, which is helpful for tree traversal algorithms.
• Minimum Moves: BFS is suitable for problems like finding the minimum number of moves in board games (e.g., snake and ladder) because it guarantees the shortest path.

Both DFS and BFS have the same time complexity. O(V + E), where V is the number of vertices and E is the number of edges. Both algorithms need to visit each node and traverse each edge.

       A
      / \
     B   C
    / \   \
   D   E   F

If we use DFS starting from A:

• Traversal: A -> B -> D -> E -> C -> F
• DFS explores down a branch as far as possible (e.g., A -> B -> D), and then backtracks.

If we use BFS starting from A:

• Traversal: A -> B -> C -> D -> E -> F
• BFS explores each level completely before moving to the next level.

For problems involving trees, DFS is used for inorder, preorder, or postorder traversals, while BFS is used for level order traversal.

Here are the example codes:

// Depth-First Search (DFS) implementation
const dfsTraversal = (graph, start) => {
    const visited = new Set();
    const result = [];

    const dfs = (node) => {
        if (!node || visited.has(node)) return;
        visited.add(node);
        result.push(node);

        for (let neighbor of graph.get(node) || []) {
            dfs(neighbor);
        }
    };

    dfs(start);
    return result;
};

// Breadth-First Search (BFS) implementation
const bfsTraversal = (graph, start) => {
    const visited = new Set();
    const queue = [start];
    const result = [];

    while (queue.length > 0) {
        const node = queue.shift();
        if (!node || visited.has(node)) continue;

        visited.add(node);
        result.push(node);

        for (let neighbor of graph.get(node) || []) {
            if (!visited.has(neighbor)) {
                queue.push(neighbor);
            }
        }
    }

    return result;
};

// Example Graph Representation and Traversal
const graph = new Map();
graph.set('A', ['B', 'C']);
graph.set('B', ['D', 'E']);
graph.set('C', ['F']);
graph.set('D', []);
graph.set('E', ['F']);
graph.set('F', []);

// Example usage:
console.log('DFS Traversal:', dfsTraversal(graph, 'A')); // Output: [ 'A', 'B', 'D', 'E', 'F', 'C' ]
console.log('BFS Traversal:', bfsTraversal(graph, 'A')); // Output: [ 'A', 'B', 'C', 'D', 'E', 'F' ]

Cheers 🫶🏻