DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Depth First Search (DFS)

What Is DFS on a Graph?

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a stack (or the call stack via recursion) to track the current exploration path.

Reference graph (undirected):

     0 ─── 1 ─── 3
     │     │
     2 ─── 4 ─── 5

DFS from vertex 0 (neighbour order: sorted ascending):

  Visit 0  → push 0's unvisited neighbours [1, 2]
  Visit 1  → push 1's unvisited neighbours [3, 4]
  Visit 3  → no unvisited neighbours → backtrack
  Visit 4  → push 4's unvisited neighbour [5]  (2 already visited? no yet)
  Visit 5  → no unvisited neighbours → backtrack
  Backtrack to 1 → all done
  Backtrack to 0 → visit 2 → 2's neighbours: 0 (visited), 4 (visited) → done

DFS order: 0, 1, 3, 4, 5, 2

Compare with BFS order: 0, 1, 2, 3, 4, 5
DFS dives deep; BFS fans wide.

Recursive vs Iterative DFS

RECURSIVE DFS:
  Uses the CALL STACK to remember which vertex to return to.
  Clean and concise — mirrors the natural recursive structure.
  Risk: stack overflow for very deep graphs (>~10,000 levels in Python).

ITERATIVE DFS:
  Uses an EXPLICIT STACK data structure.
  Same logic but manually managed.
  Avoids call stack overflow.
  Note: iterative DFS with push(right then left) visits left first
        — mirror the recursive order carefully.

Core DFS Implementation

Java

Try it out

import java.util.*;

public class GraphDFS {

    // RECURSIVE DFS — O(V + E)
    public static List<Integer> dfsRecursive(List<List<Integer>> adj, int V) {
        List<Integer> order   = new ArrayList<>();
        boolean[]     visited = new boolean[V];

        for (int start = 0; start < V; start++) {
            if (!visited[start]) {
                dfsHelper(adj, start, visited, order);
            }
        }
        return order;
    }

    private static void dfsHelper(List<List<Integer>> adj, int u,
                                   boolean[] visited, List<Integer> order) {
        visited[u] = true;
        order.add(u);

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfsHelper(adj, v, visited, order);
            }
        }
    }

    // ITERATIVE DFS — same result as recursive (same neighbour order)
    public static List<Integer> dfsIterative(List<List<Integer>> adj, int V) {
        List<Integer> order   = new ArrayList<>();
        boolean[]     visited = new boolean[V];

        for (int start = 0; start < V; start++) {
            if (visited[start]) continue;

            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);

            while (!stack.isEmpty()) {
                int u = stack.pop();
                if (visited[u]) continue;   // May be pushed multiple times

                visited[u] = true;
                order.add(u);

                // Push neighbours in REVERSE order to match recursive visit order
                List<Integer> neighbours = adj.get(u);
                for (int i = neighbours.size() - 1; i >= 0; i--) {
                    int v = neighbours.get(i);
                    if (!visited[v]) stack.push(v);
                }
            }
        }
        return order;
    }

    // DFS with path finding — returns path from src to dst, or empty if none
    public static List<Integer> findPath(List<List<Integer>> adj, int src,
                                          int dst, int V) {
        boolean[]     visited = new boolean[V];
        List<Integer> path    = new ArrayList<>();
        dfsPath(adj, src, dst, visited, path);
        return path;
    }

    private static boolean dfsPath(List<List<Integer>> adj, int u, int dst,
                                    boolean[] visited, List<Integer> path) {
        visited[u] = true;
        path.add(u);

        if (u == dst) return true;   // Found destination

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                if (dfsPath(adj, v, dst, visited, path)) return true;
            }
        }

        path.remove(path.size() - 1);   // Backtrack — remove u from path
        return false;
    }

    public static void main(String[] args) {
        int V = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{0,2},{1,3},{1,4},{2,4},{4,5}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]);
        }

        System.out.println("Recursive DFS: " + dfsRecursive(adj, V));
        // [0, 1, 3, 4, 2, 5]  (order depends on adjacency list)

        System.out.println("Iterative DFS: " + dfsIterative(adj, V));
        // Same order as recursive

        System.out.println("Path 0→5: " + findPath(adj, 0, 5, V));
        // [0, 1, 4, 5]
    }
}

Output:
Recursive DFS: [0, 1, 3, 4, 2, 5]
Iterative DFS: [0, 1, 3, 4, 2, 5]
Path 0→5:      [0, 1, 4, 5]

Dry Run: DFS on a Graph

Graph (undirected):
     0 ─── 1 ─── 3
     │     │
     2 ─── 4 ─── 5

Adjacency list:
  0: [1, 2]
  1: [0, 3, 4]
  2: [0, 4]
  3: [1]
  4: [1, 2, 5]
  5: [4]

DFS from 0 (recursive — visit first unvisited neighbour):

Call dfs(0): visited={0}, order=[0]
  Neighbour 1: unvisited → Call dfs(1): visited={0,1}, order=[0,1]
    Neighbour 0: visited → skip
    Neighbour 3: unvisited → Call dfs(3): visited={0,1,3}, order=[0,1,3]
      Neighbour 1: visited → skip
      No more → RETURN (backtrack to 1)
    Neighbour 4: unvisited → Call dfs(4): visited={0,1,3,4}, order=[0,1,3,4]
      Neighbour 1: visited → skip
      Neighbour 2: unvisited → Call dfs(2): visited={0,1,2,3,4}, order=[0,1,3,4,2]
        Neighbour 0: visited → skip
        Neighbour 4: visited → skip
        No more → RETURN (backtrack to 4)
      Neighbour 5: unvisited → Call dfs(5): visited={0,1,2,3,4,5}, order=[0,1,3,4,2,5]
        Neighbour 4: visited → skip
        No more → RETURN (backtrack to 4)
      No more → RETURN (backtrack to 1)
    No more → RETURN (backtrack to 0)
  Neighbour 2: visited → skip
  No more → RETURN

Final DFS order: [0, 1, 3, 4, 2, 5]

Application 1: Cycle Detection — Undirected Graph

UNDIRECTED CYCLE DETECTION:
  A cycle exists if DFS visits a node that is already visited
  AND that node is NOT the direct parent of the current node.

     0 ─── 1
     │     │
     2 ─── 3    ← cycle: 0-1-3-2-0

DFS from 0 with parent tracking:
  dfs(0, parent=-1):
    Visit 1 (parent=0): dfs(1, parent=0)
      Visit 3 (parent=1): dfs(3, parent=1)
        Visit 2 (parent=3): dfs(2, parent=3)
          Neighbour 0: visited AND 0 ≠ parent(3) → CYCLE DETECTED!

Java

Try it out

public class CycleDetection {

    static class Graph {
        List<List<Integer>> adj;
        int V;
        Graph(int V) {
            this.V = V;
            adj = new ArrayList<>();
            for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        }
        void addEdge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); }
    }

    // UNDIRECTED: track parent to distinguish back edges from tree edges
    public static boolean hasCycleUndirected(Graph g) {
        boolean[] visited = new boolean[g.V];

        for (int start = 0; start < g.V; start++) {
            if (!visited[start]) {
                if (dfsCycleUndirected(g, start, -1, visited)) return true;
            }
        }
        return false;
    }

    private static boolean dfsCycleUndirected(Graph g, int u, int parent,
                                               boolean[] visited) {
        visited[u] = true;

        for (int v : g.adj.get(u)) {
            if (!visited[v]) {
                if (dfsCycleUndirected(g, v, u, visited)) return true;
            } else if (v != parent) {
                // Visited AND not the parent → back edge → cycle!
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // Cyclic graph: 0─1─3─2─0
        Graph cyclic = new Graph(4);
        cyclic.addEdge(0, 1); cyclic.addEdge(1, 3);
        cyclic.addEdge(3, 2); cyclic.addEdge(2, 0);
        System.out.println("Cyclic: " + hasCycleUndirected(cyclic));   // true

        // Acyclic graph: 0─1─2, 1─3
        Graph acyclic = new Graph(4);
        acyclic.addEdge(0, 1); acyclic.addEdge(1, 2); acyclic.addEdge(1, 3);
        System.out.println("Acyclic: " + hasCycleUndirected(acyclic)); // false
    }
}

Output:
Cyclic:   true
Acyclic:  false

Application 2: Cycle Detection — Directed Graph

DIRECTED CYCLE DETECTION:
  For directed graphs, we need an additional inStack[] array.
  inStack[u] = true if u is currently on the active DFS path.

  Why visited[] alone is insufficient:
     A ──→ B
     ↑     │
     C ←───┘

    DFS: A → B → C → A?  No: C→A is a directed cycle.
    But consider:  A → B → C and D → C
    When visiting D→C, C is already visited (from A→B→C path).
    But C is NOT on the current stack (D's path).
    So this is NOT a cycle — D can reach C via a separate path.

  RULE: cycle exists if we reach a node currently in inStack (gray node).
        Reaching a fully-finished node (not in stack) is NOT a cycle.

Java

Try it out

public class DirectedCycleDetection {

    public static boolean hasCycleDirected(List<List<Integer>> adj, int V) {
        boolean[] visited = new boolean[V];
        boolean[] inStack = new boolean[V];  // Recursion stack

        for (int start = 0; start < V; start++) {
            if (!visited[start]) {
                if (dfsCycleDirected(adj, start, visited, inStack)) return true;
            }
        }
        return false;
    }

    private static boolean dfsCycleDirected(List<List<Integer>> adj, int u,
                                             boolean[] visited,
                                             boolean[] inStack) {
        visited[u] = true;
        inStack[u] = true;   // Mark as part of current DFS path

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                if (dfsCycleDirected(adj, v, visited, inStack)) return true;
            } else if (inStack[v]) {
                // v is on the current path → back edge → DIRECTED CYCLE!
                return true;
            }
        }

        inStack[u] = false;  // Remove from current path (backtrack)
        return false;
    }

    public static void main(String[] args) {
        int V = 4;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());

        // Cyclic directed: 0→1→2→0
        adj.get(0).add(1); adj.get(1).add(2); adj.get(2).add(0);
        System.out.println("Directed cycle:    " + hasCycleDirected(adj, V)); // true

        // Reset — DAG: 0→1→2→3
        List<List<Integer>> dag = new ArrayList<>();
        for (int i = 0; i < V; i++) dag.add(new ArrayList<>());
        dag.get(0).add(1); dag.get(1).add(2); dag.get(2).add(3);
        System.out.println("Directed no cycle: " + hasCycleDirected(dag, V)); // false
    }
}

Output:
Directed cycle:    true
Directed no cycle: false
Cross edges:       false

Application 3: Topological Sort (DFS Post-Order)

Topological sort orders vertices so that for every directed edge u→v, u comes before v. Only works on DAGs.

DAG:
     5 ──→ 0
     5 ──→ 2
     4 ──→ 0
     4 ──→ 1
     2 ──→ 3
     3 ──→ 1

DFS POST-ORDER (add vertex AFTER all descendants are finished):

  dfs(5): → dfs(0): leaf → add 0 to result
          → dfs(2): → dfs(3): → dfs(1): leaf → add 1
                              → add 3
                    → add 2
          → add 5
  dfs(4): → 0 visited
          → 1 visited
          → add 4

Result (post-order, added at finish): [0, 1, 3, 2, 5, 4]
REVERSE to get topological order:     [4, 5, 2, 3, 1, 0]

VERIFY: every edge u→v has u before v in [4, 5, 2, 3, 1, 0]:
  5→0: 5 before 0 ✓    5→2: 5 before 2 ✓
  4→0: 4 before 0 ✓    4→1: 4 before 1 ✓
  2→3: 2 before 3 ✓    3→1: 3 before 1 ✓  All correct!

Java

Try it out

import java.util.*;

public class TopologicalSortDFS {

    public static List<Integer> topologicalSort(List<List<Integer>> adj, int V) {
        boolean[]     visited = new boolean[V];
        Deque<Integer> stack  = new ArrayDeque<>();  // Result stack (post-order)

        for (int start = 0; start < V; start++) {
            if (!visited[start]) {
                topoHelper(adj, start, visited, stack);
            }
        }

        // Pop stack to get topological order (reversed post-order)
        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) result.add(stack.pop());
        return result;
    }

    private static void topoHelper(List<List<Integer>> adj, int u,
                                    boolean[] visited, Deque<Integer> stack) {
        visited[u] = true;

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                topoHelper(adj, v, visited, stack);
            }
        }

        stack.push(u);   // Add AFTER all descendants finished (post-order)
    }

    public static void main(String[] args) {
        // DAG: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1
        int V = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(5).add(0); adj.get(5).add(2);
        adj.get(4).add(0); adj.get(4).add(1);
        adj.get(2).add(3); adj.get(3).add(1);

        System.out.println("Topological order: " + topologicalSort(adj, V));
        // [4, 5, 2, 3, 1, 0]  (one valid ordering)
    }
}

Output:
Topological order: [4, 5, 2, 3, 1, 0]

Application 4: DFS Timestamps

Assign discovery d[u] and finish f[u] times to each vertex. Useful for edge classification and strongly connected components.

DFS TIMESTAMPS — timer increments at each event:

Graph (directed): 0→1→2→3, 0→3

DFS from 0:
  d[0]=1, enter 0
    d[1]=2, enter 1
      d[2]=3, enter 2
        d[3]=4, enter 3
        f[3]=5, finish 3
      f[2]=6, finish 2
    f[1]=7, finish 1
    3 already visited → edge 0→3 is a FORWARD EDGE
  f[0]=8, finish 0

Timestamps: d=[1,2,3,4], f=[8,7,6,5]

EDGE CLASSIFICATION using timestamps (directed graph):
  Tree edge:    d[u] < d[v] AND f[v] < f[u]  (v first discovered via this edge)
  Forward edge: d[u] < d[v] AND f[v] < f[u]  (v already in subtree of u)
  Back edge:    d[v] < d[u] AND f[u] < f[v]  (u is in subtree of v — CYCLE!)
  Cross edge:   f[v] < d[u]                   (v fully done before u started)

KEY PROPERTY: Back edges exist ←→ graph has directed cycle

Java

Try it out

public class DFSTimestamps {

    private static int timer = 0;

    public static void computeTimestamps(List<List<Integer>> adj, int V) {
        int[]     d       = new int[V];    // Discovery time
        int[]     f       = new int[V];    // Finish time
        boolean[] visited = new boolean[V];
        timer = 0;

        for (int start = 0; start < V; start++) {
            if (!visited[start]) {
                dfsTime(adj, start, visited, d, f);
            }
        }

        System.out.println("Discovery: " + java.util.Arrays.toString(d));
        System.out.println("Finish:    " + java.util.Arrays.toString(f));
    }

    private static void dfsTime(List<List<Integer>> adj, int u,
                                 boolean[] visited, int[] d, int[] f) {
        visited[u] = true;
        d[u] = ++timer;   // Discovery time

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfsTime(adj, v, visited, d, f);
            }
        }

        f[u] = ++timer;   // Finish time (all descendants done)
    }

    public static void main(String[] args) {
        int V = 4;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(1); adj.get(1).add(2);
        adj.get(2).add(3); adj.get(0).add(3);
        computeTimestamps(adj, V);
        // Discovery: [1, 2, 3, 4]   Finish: [8, 7, 6, 5]
    }
}

Output:
Discovery: [1, 2, 3, 4]
Finish:    [8, 7, 6, 5]

DFS vs BFS — When to Use Which

USE DFS WHEN:                         USE BFS WHEN:
  Cycle detection                       Shortest path (unweighted)
  Topological sort                      Level-by-level processing
  Finding ANY path (not shortest)       Minimum steps / hops
  Exploring all paths                   Nearest something (multi-source)
  Connected components                  Social graph distance
  Strongly connected components         0-1 BFS for 0/1 weights
  Backtracking / exhaustive search      Checking bipartiteness
  Maze solving (any solution)           Finding all nodes at distance k
  DFS tree / timestamps                 BFS spanning tree
  Detecting back edges

BOTH WORK FOR:
  Connected component count (O(V+E))
  Graph traversal
  Cycle detection (different techniques)
  Reachability queries

MEMORY:
  DFS: O(h) stack space where h = max DFS depth
       (O(V) worst case for skewed graphs / long paths)
  BFS: O(w) queue space where w = max level width
       (O(V) worst case for star graphs with all nodes at level 1)

Complexity Summary

Operation	Time	Space	Notes
DFS traversal	O(V + E)	O(V)	visited array + call stack
Cycle detection (undirected)	O(V + E)	O(V)	Track parent
Cycle detection (directed)	O(V + E)	O(V)	Track inStack
Topological sort	O(V + E)	O(V)	Post-order + reverse
DFS timestamps	O(V + E)	O(V)	d[] and f[] arrays
Connected components	O(V + E)	O(V)	Outer loop + DFS
Path finding	O(V + E)	O(V)	Backtracking path

Common Mistakes

Using visited[] alone for directed cycle detection. In directed graphs, a visited node in the global visited set does not mean a cycle — it may have been visited via a completely different DFS path. Only a node currently on the ACTIVE recursion stack (inStack[v] = true) indicates a back edge and a directed cycle. Always use a separate inStack array for directed cycle detection.

Forgetting inStack[u] = false when backtracking. After exploring all of u's neighbours, u must be removed from the recursion stack (inStack[u] = false). Forgetting this causes false cycle detections — future DFS paths will incorrectly see u as "currently on stack."

Topological sort: adding vertex to result at DFS entry instead of exit. Adding a vertex to the topological result when first visiting it (pre-order) gives the wrong order. The vertex must be added AFTER all of its descendants are fully explored (post-order). Then reverse the result. Pre-order gives DFS traversal order, not topological order.

Iterative DFS not matching recursive DFS order. Iterative DFS with a stack and pushing neighbours left-to-right will visit right-to-left (LIFO). To match recursive DFS, push neighbours in reverse order (right-to-left push, so left is on top and visited first). If exact order doesn't matter (for connectivity), this is fine.

Applying topological sort to a cyclic graph. If the graph has a cycle, no topological ordering exists. Always verify the graph is a DAG first (run cycle detection), or check the output: if the topological sort didn't include all V vertices (some were never added), a cycle prevented them from being finished.

Interview Questions

Q: What is the key difference between cycle detection in undirected vs directed graphs?

Undirected: a cycle is detected when DFS reaches a visited node that is NOT the direct parent of the current node. The parent check is needed because in undirected graphs, the edge from child back to parent is not a cycle — it's the same undirected edge traversed backwards. Directed: a cycle is detected only when DFS reaches a node currently in the active recursion stack (inStack = true). Reaching a visited node NOT in the stack means it was explored in a previous DFS path — no cycle.

Q: Why is topological sort impossible on a cyclic graph?

Topological sort requires every edge u→v to have u before v in the ordering. In a cycle A→B→C→A: A must come before B (edge A→B), B before C, C before A. But A before B and C before A means A comes both before and after B simultaneously — impossible. There is no linear ordering that satisfies all constraints simultaneously. Kahn's algorithm detects this when not all vertices are processed; DFS-based detects it via back edges.

Q: What are DFS timestamps used for beyond edge classification?

DFS timestamps (discovery d[u] and finish f[u]) enable: (1) Edge classification — back/forward/cross/tree edges in O(1) per edge using timestamp comparison. (2) Kosaraju's SCC algorithm — the finish order from DFS on the original graph determines the DFS order on the reversed graph. (3) Identifying articulation points and bridges in undirected graphs. (4) Parenthesis structure — the intervals [d[u], f[u]] for any two nodes are either disjoint or one contains the other, mirroring the parenthesis nesting of function calls.

Summary

DFS explores a graph by going as deep as possible along each branch using a stack (or recursion). It visits each vertex once and each edge once — O(V + E).

Two implementations:

›Recursive — uses call stack; clean, concise, risk of stack overflow for very deep graphs
›Iterative — uses explicit stack; push neighbours in reverse order to match recursive visit order

Four key applications:

Application	Unique technique
Cycle detection (undirected)	Track parent; cycle if visited neighbour ≠ parent
Cycle detection (directed)	Track inStack; cycle if visited neighbour is in current stack
Topological sort	Add vertex at DFS exit (post-order); reverse the result
DFS timestamps	d[u] = entry time, f[u] = exit time; classify edges by interval containment

DFS vs BFS choice:

›Path finding, cycle detection, topological sort, backtracking → DFS
›Shortest path, level-by-level, nearest node → BFS

In the next topic you will explore Shortest Path Algorithms — Dijkstra's, Bellman-Ford, and Floyd-Warshall for weighted graphs.

Suggested Quiz

DFS uses a stack (or recursion). How does this differ from BFS in exploration order?

1/6

←

PreviousBreadth First Search (BFS)

NextConnected Components

→