What is the difference between DFS and BFS?

DFS explores depth-first (uses stack), going as deep as possible before backtracking. BFS explores breadth-first (uses queue), visiting all nodes at current level before next level. DFS uses less memory (O(h)) but doesn't find shortest path.

Why does DFS use a stack?

Stack provides LIFO (Last In First Out) behavior, ensuring the most recently discovered node is explored next. This gives depth-first exploration - going deep before exploring other branches.

Can DFS find shortest path?

No, DFS doesn't guarantee shortest path. It finds any path. For shortest path in unweighted graphs, use BFS. For weighted graphs, use Dijkstra's or A* algorithm.

What is the time complexity of DFS?

O(V + E) where V is number of vertices and E is number of edges. For trees, this simplifies to O(V) since E = V-1.

When should I use DFS instead of BFS?

Use DFS when memory is limited, when you need to explore deep paths, for tree problems (pre/in/post-order), or when you don't need shortest path. Use BFS when you need shortest path or level-order traversal.

Depth-First Search Explained Step by Step (Complete Guide)

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's like exploring a maze by always taking the leftmost path until you hit a dead end, then backtracking to try the next path.

In this comprehensive guide, you'll learn how DFS works with step-by-step examples, visualizations, both recursive and iterative implementations, and real-world use cases. We'll make it easy to understand with clear explanations.

💡 Quick Tip

Use our free JSON Validator to validate tree structures and our JSON Formatter to visualize hierarchical data.

Definition: What Is Depth-First Search?

Depth-First Search (DFS) is a graph traversal algorithm that explores as deeply as possible along each branch before backtracking. It uses a stack (either explicit or via recursion) to keep track of nodes to visit.

Key characteristics of DFS:

Go Deep First

Explores one path completely before trying another

Uses Stack

LIFO (Last In First Out) structure

Memory Efficient

Uses less memory than BFS (O(h) vs O(w))

Backtracking

Returns to previous node when path ends

Real-World Analogy

Imagine exploring a cave system. DFS is like following one tunnel all the way to the end, marking your path, then backtracking to explore the next tunnel. You go as deep as possible before trying another path.

What Does DFS Do?

DFS systematically explores a graph or tree by:

1. Starting at a Node

Begins at a starting node (usually the root in trees)

2. Going Deep

Follows one path as far as possible before backtracking

3. Using Stack/Recursion

Maintains a stack of nodes to visit, processing most recent first

4. Backtracking

Returns to previous node when no more unvisited neighbors

When to Use DFS?

Use DFS in these scenarios:

Path finding - Finding any path between two nodes

Cycle detection - Detecting cycles in graphs

Topological sorting - Ordering nodes in directed acyclic graphs

Tree/graph problems - Many tree problems use DFS naturally

Memory constraints - When memory is limited (DFS uses less than BFS)

How DFS Works: Step-by-Step Example

Example Tree

/ \

2 3

/ \ / \

4 5 6 7

DFS Traversal Steps (Pre-order)

Start: Visit 1, Stack = [1]

Visit node 1, go to left child (2)

Path: [1] | Stack: [2, 3]

Visit: 2, Stack = [2, 3]

Visit node 2, go to left child (4)

Path: [1, 2] | Stack: [4, 5, 3]

Visit: 4, Stack = [4, 5, 3]

Visit node 4 (leaf), backtrack to 2

Path: [1, 2, 4] | Stack: [5, 3]

Backtrack: Visit 5, Stack = [5, 3]

Backtracked to 2, now visit right child (5)

Path: [1, 2, 4, 5] | Stack: [3]

Backtrack: Visit 3, Stack = [3]

Backtracked to 1, now visit right child (3)

Path: [1, 2, 4, 5, 3] | Stack: [6, 7]

6-7

Visit: 6, 7

Visit nodes 6 and 7 (leaves)

Path: [1, 2, 4, 5, 3, 6, 7] | Stack: []

✓

Result: DFS Order = [1, 2, 4, 5, 3, 6, 7]

All nodes visited depth-first!

DFS Code Implementation (Recursive)

// Recursive DFS (Pre-order)

function

dfs

(node, visited =

new

Set

(), result = []) {

(!node || visited.has(node))

return

result;

visited.add(node);

result.push(node.val);

// Visit node

for

(

const

child of node.children) {

dfs(child, visited, result);

// Recursive call

}

return

result;

}

DFS Code Implementation (Iterative)

// Iterative DFS using stack

function

dfsIterative

(root) {

(!root)

return

[];

const

stack = [root];

const

result = [];

const

visited =

new

Set

();

while

(stack.length >

) {

const

node = stack.pop();

// Remove from end

(visited.has(node))

continue

;

visited.add(node);

result.push(node.val);

// Add children in reverse order (for correct traversal)

for

(let i = node.children.length -

; i >=

; i--) {

stack.push(node.children[i]);

}

return

result;

}

DFS Algorithm Flow

Start

Start at Root Node

Stack = [root], Visited =

Is Stack Empty?

Yes → Done

Return result

No → Continue

Process next node

Pop Node from Stack

Remove from end (LIFO)

Mark as Visited & Process

Add to result, mark visited

Push Children to Stack

Add unvisited children to end of stack

Loop

Repeat Until Stack Empty

Go back to check stack

DFS Traversal Variants

Pre-order (Root → Left → Right)

Visit root, then left subtree, then right subtree

Example: [1, 2, 4, 5, 3, 6, 7]

In-order (Left → Root → Right)

Visit left subtree, then root, then right subtree

Example: [4, 2, 5, 1, 6, 3, 7]

Post-order (Left → Right → Root)

Visit left subtree, then right subtree, then root

Example: [4, 5, 2, 6, 7, 3, 1]

DFS Time & Space Complexity

Metric	Complexity	Explanation
Time Complexity	O(V + E)	V = vertices, E = edges. Visit each node once, check each edge once
Space Complexity	O(h)	h = height. Stack depth equals tree height (worst case)
For Tree (V nodes)	O(V)	In trees, E = V-1, so O(V + E) = O(V)

Why Use DFS?

Memory Efficient

Uses O(h) space vs O(w) for BFS (h = height, w = width)

Natural for Trees

Many tree problems naturally use DFS (pre/in/post-order)

Path Finding

Good for finding any path, not necessarily shortest

Simple Recursion

Can be implemented elegantly with recursion

Real-World DFS Applications

1. File System Traversal

Exploring directory structures, finding files recursively

Example: Finding all .txt files in a directory tree

2. Cycle Detection

Detecting cycles in directed/undirected graphs

Example: Detecting circular dependencies in build systems

3. Topological Sorting

Ordering nodes in directed acyclic graphs (DAGs)

Example: Task scheduling, course prerequisites

4. Maze Solving

Finding paths through mazes (any path, not shortest)

Example: Game AI pathfinding, puzzle solving

Definition: What Is Depth-First Search?

Go Deep First

Uses Stack

Memory Efficient

Backtracking

Real-World Analogy

What Does DFS Do?

1. Starting at a Node

2. Going Deep

3. Using Stack/Recursion

4. Backtracking

When to Use DFS?

How DFS Works: Step-by-Step Example

Example Tree

DFS Traversal Steps (Pre-order)

Start: Visit 1, Stack = [1]

Visit: 2, Stack = [2, 3]

Visit: 4, Stack = [4, 5, 3]

Backtrack: Visit 5, Stack = [5, 3]

Backtrack: Visit 3, Stack = [3]

Visit: 6, 7

Result: DFS Order = [1, 2, 4, 5, 3, 6, 7]

DFS Code Implementation (Recursive)

DFS Code Implementation (Iterative)

DFS Algorithm Flow

Start at Root Node

Is Stack Empty?

Pop Node from Stack

Mark as Visited & Process

Push Children to Stack

Repeat Until Stack Empty

DFS Traversal Variants

Pre-order (Root → Left → Right)

In-order (Left → Root → Right)

Post-order (Left → Right → Root)

DFS Time & Space Complexity

Why Use DFS?

Memory Efficient

Natural for Trees

Path Finding

Simple Recursion

Real-World DFS Applications

1. File System Traversal

2. Cycle Detection

3. Topological Sorting

4. Maze Solving

Share this article with Your Friends, Collegue and Team mates

Stay Updated