DFS VS BFS

Applicable Scenarios for DFS and BFS

By the end of this article you will understand the core patterns behind both algorithms and be ready to solve problems such as the one shown below:

Prerequisites

Before continuing, make sure you are comfortable with:

Recursive traversal and level-order traversal of a binary tree

In practice, depth-first search (DFS) is frequently chosen when the goal is to enumerate every possible path, while breadth-first search (BFS) is preferred when the goal is to find the shortest path. The reason becomes clear once you examine the simplest versions of each approach—ordinary recursive traversal (DFS) and level-order traversal (BFS)—on a binary tree.

Why BFS Is Naturally Suited to Shortest-Path Problems

Consider LeetCode 111, “Minimum Depth of Binary Tree”:

Given a binary tree, return its minimum depth. The minimum depth is the number of nodes along the shortest path from the root to the nearest leaf node. A leaf is a node that has no children.

Example 1
Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints

The number of nodes in the tree is in the range [0, 10^5]

-1000 <= Node.val <= 1000

Source: LeetCode 111. Minimum Depth of Binary Tree.

The problem asks for the length of the shortest root-to-leaf path, so it is fundamentally a shortest-path question. Both a recursive DFS and a level-order BFS can solve it; we begin with the DFS version.

class Solution:
    def __init__(self):
        # tracks the smallest root-to-leaf depth seen so far
        self.min_depth = float('inf')
        # tracks the depth of the node currently being visited
        self.curr_depth = 0

    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0

        self.dfs(root)
        return self.min_depth

    def dfs(self, node: TreeNode) -> None:
        if node is None:
            return

        # entering a node: depth increases
        self.curr_depth += 1

        # leaf node: possibly update the global minimum
        if node.left is None and node.right is None:
            self.min_depth = min(self.min_depth, self.curr_depth)

        self.dfs(node.left)
        self.dfs(node.right)

        # leaving a node: depth decreases
        self.curr_depth -= 1

If you step through the recursive calls, you will see that the algorithm walks the tree branch by branch from left to right. Each time a leaf is reached, the length of that particular branch is compared with the best answer found so far. Only after every branch has been examined can the true minimum be known; there is no safe way to stop early, because an unexplored branch might be shorter.

Now contrast this with the BFS solution. Because BFS processes nodes level by level, the first leaf it encounters is guaranteed to be the closest one to the root:

class Solution:
    def minDepth(self, root: TreeNode | None) -> int:
        return self.levelOrderTraverse(root)
    
    def levelOrderTraverse(self,root):
        if root is None:
            return 0
        
        q = [root]
        depth = 1
        while len(q)!=0:
            size = len(q)
            for i in range(size):
                node = q[i]
                if node.left is None and node.right is None:
                    return depth
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            depth+=1
            q = q[size:]
        
        return depth

Watching the queue grow, you will notice that the algorithm finishes as soon as it reaches the second level and finds a leaf. It never needs to visit the rest of the tree.

This behavior explains why BFS is the usual choice for shortest-path problems: the first time the target is reached, the path taken is guaranteed to be a shortest path, and the search can often terminate without examining every node. DFS can also compute a shortest path, but only after it has explored the entire search space. In the worst case both algorithms visit every node and therefore run in O(N) time; in typical cases, however, BFS finishes earlier and is therefore more efficient. Consequently, when the task is to find a shortest path, BFS is the preferred tool.

Why DFS Is Naturally Suited to Enumerating All Paths

When the task changes to collecting every root-to-leaf path, the situation reverses: DFS appears far more often than BFS. Both traversals are theoretically capable of producing the complete set of paths, yet the BFS implementation quickly becomes cumbersome. Inside the queue you can no longer store bare nodes; you must also carry the path that led to each node. That requires an auxiliary state object (or an equivalent pair) and extra bookkeeping at every step—the “third style” of level-order traversal.

DFS, by contrast, already walks one complete branch at a time. When the recursion reaches a leaf, the sequence of nodes currently on the call stack is exactly one root-to-leaf path. No auxiliary path structure is required; the recursion itself supplies the path. This makes the DFS code both shorter and easier to reason about.

If you compare the two visualizations side by side, the difference is striking: the DFS version simply appends a node on the way down and removes it on the way up, while the BFS version must allocate and copy path lists (or state objects) for every node in the queue. The extra complexity is why practitioners almost always reach for DFS when the goal is to enumerate all paths.

Summary

DFS is the algorithm of choice when you need every possible path; BFS is the algorithm of choice when you need the shortest path. The difference follows directly from the order in which each algorithm explores the tree.