SoftwareInLevels

Understanding BFS vs DFS — Implementation Guide

Dive into the technical implementation of BFS and DFS. Learn about queue vs stack data structures, iterative vs recursive approaches, and see production-ready code in multiple languages.

Author

Mr. Oz

Date

Read

8 mins

Level 2
Code implementation showing BFS using queue and DFS using stack with visual diagram

Author

Mr. Oz

Date

Read

8 mins

Share

Twitter YouTube

Now that you understand the conceptual difference between BFS and DFS from Level 1, let's dive into how to implement them in code. The key insight is understanding which data structure each uses.

The Data Structure Connection

The fundamental difference between BFS and DFS comes down to one choice: how do we store nodes to visit next?

BFS Uses a QUEUE

First-In-First-Out (FIFO)

Process nodes in the order they were discovered → level by level

DFS Uses a STACK

Last-In-First-Out (LIFO)

Process most recently discovered nodes first → go deep

BFS Implementation (Python)

from collections import deque

def bfs(root):
    if not root:
        return []

    result = []
    queue = deque([root])  # Queue for BFS

    while queue:
        node = queue.popleft()  # FIFO: remove from front
        result.append(node.val)

        # Add children to back of queue
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result

Key: popleft() removes from front (FIFO), ensuring we process level by level.

DFS Implementation - Iterative (Python)

def dfs_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]  # Stack for DFS

    while stack:
        node = stack.pop()  # LIFO: remove from end
        result.append(node.val)

        # Add children to stack (right first, so left is processed first)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Key: pop() removes from end (LIFO), ensuring we go deep before going wide.

DFS Implementation - Recursive (Python)

def dfs_recursive(root):
    result = []

    def traverse(node):
        if not node:
            return

        result.append(node.val)    # Pre-order
        traverse(node.left)        # Recurse left
        traverse(node.right)       # Recurse right

    traverse(root)
    return result

The call stack naturally implements LIFO behavior! Each recursive call adds to the stack.

Complexity Comparison

Metric BFS DFS
Time Complexity O(n) O(n)
Space (Worst) O(w) - max width O(h) - max height
Best for Shortest Path Yes No
Memory (Balanced Tree) O(n/2) ≈ O(n) O(log n)

Key insight: For a balanced tree, DFS uses less memory (O(log n) vs O(n)) because it only stores one path at a time, while BFS stores an entire level.

Common Pitfalls

  • Forgetting to check null: Always check if node is null before accessing children
  • Wrong child order in DFS stack: Push right first if you want left-to-right traversal
  • Not tracking visited nodes (graphs): In graphs, always mark nodes as visited to avoid infinite loops
  • Stack overflow with recursive DFS: For very deep trees, use iterative DFS to avoid stack overflow

Continue Learning

← Level 1: The Basics Level 3: Advanced Optimization →

Key Takeaways

  • BFS uses a queue (FIFO); DFS uses a stack (LIFO)
  • DFS can be recursive (uses call stack) or iterative (explicit stack)
  • Both have O(n) time complexity, but space differs based on tree shape
  • BFS is best for shortest path problems
  • DFS is best for memory-constrained situations or finding any path

All Levels