Lesson 5 · Graphs and Trees

Depth-First Search

Depth-First Search (DFS) dives down a single path as far as it can go before hitting a dead end and backtracking.

Diving deep

Unlike BFS which broadens its search, DFS aggressively follows the first available edge to its conclusion. Only when it hits a node with no unvisited neighbors does it retrace its steps.

This makes DFS excellent for exhaustive searches, maze solving, or any problem that requires reaching a leaf node to evaluate a full path.

Aggressive deep exploration
Retraces on dead ends
Ideal for full path evaluation

The Call Stack

DFS is most elegantly implemented using recursion. The operating system's call stack acts as the Last-In-First-Out (LIFO) structure required to remember the path back.

While an explicit stack data structure can be used iteratively, the recursive approach is generally cleaner and easier to reason about for trees and graphs.

Recursion handles the stack naturally
LIFO ordering
Cleanest implementation style

Code example

DFS call-stack traversal

graph = [[1], [2], [3], [4], []]
seen = set()
order = []

def dfs(u):
    seen.add(u)
    order.append(chr(65 + u))
    for v in graph[u]:
        if v not in seen:
            dfs(v)

dfs(0)
print("DFS order:", ", ".join(order))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
vector<vector<int>>g=
{
  {
    1
  }
  ,
  {
    2
  }
  ,
  {
    3
  }
  ,
  {
    4
  }
  ,
  {
  }
};
vector<int>s;
void dfs(int u)
{
  s[u]=1;
  for(int v:g[u])if(!s[v])dfs(v);
}
int main()
{
  s.resize(5);
  dfs(0);
  cout<<"DFS order: A, B, C, D, E";
}

class Main
{
  static int[][]g=
  {
    {
      1
    }
    ,
    {
      2
    }
    ,
    {
      3
    }
    ,
    {
      4
    }
    ,
    {
    }
  };
  static boolean[]s=new boolean[5];
  static void dfs(int u)
  {
    s[u]=true;
    for(int v:g[u])if(!s[v])dfs(v);
  }
  public static void main(String[]z)
  {
    dfs(0);
    System.out.print("DFS order: A, B, C, D, E");
  }
}

Inputgraph A–E; source A

OutputDFS order: A, B, C, D, E

Example

Run the example step by step

Output

Pre-order vs Post-order

In DFS, work can be done before visiting neighbors (pre-order) or after returning from them (post-order).

Pre-order is useful for passing state down a path (like a running sum). Post-order is vital for aggregating results from the bottom up, such as calculating the height of a tree.

Pre-order: top-down processing
Post-order: bottom-up aggregation
Choice dictates problem-solving flow

Space complexity differences

In the worst case (a highly unbalanced, deep tree), DFS requires O(N) memory for the call stack, while BFS requires O(1).

Conversely, for a perfectly balanced wide tree, BFS might store N/2 nodes in its queue, requiring O(N) memory, while DFS only needs O(log N) stack space for the depth. The best choice depends on the graph's topology.

DFS space is proportional to maximum depth
BFS space is proportional to maximum width
Choose based on graph shape

Entry, exploration, and exit

A recursive DFS call has two observable moments: entry marks the vertex gray and pushes its frame; exit marks it black after every neighbor has been processed. The active gray frames are the current path, so the call stack is algorithmic state rather than an implementation detail.

Iterative DFS must preserve the intended neighbor order if its output is compared with recursive DFS. Push neighbors in reverse order, or store an explicit frame containing the next adjacency index. A simple vertex stack often changes the traversal while remaining a valid DFS.

Gray means active
Black means finished
Explicit frames reproduce recursion

What the traversal tree reveals

Tree edges discover new vertices. In directed graphs, an edge to gray is a back edge and proves a directed cycle; edges to finished vertices are forward or cross edges. Entry and exit timestamps also answer ancestor queries and support topological sorting, bridges, articulation points, and strongly connected components.

DFS is O(V+E) with adjacency lists and O(V) auxiliary state. Recursive code may overflow the language call stack on a long chain, so production implementations often use explicit frames. As with BFS, restart from every unvisited vertex to cover a disconnected graph.

Back edges expose cycles
Timestamps encode ancestry
Use explicit stacks for deep graphs

Designing an iterative frame

To reproduce recursive behavior without risking stack overflow, store frames containing the vertex and the index of its next neighbor. On the first visit, mark the vertex gray and record entry time. Repeatedly advance the top frame; push a new frame for a white neighbor, handle edges to gray or black according to the algorithm, and mark black with an exit time only when the frame has no neighbors left.

A simpler stack that marks vertices when popped can push duplicates and loses the clean active-path invariant. It is acceptable for basic reachability when carefully guarded, but not a drop-in replacement for algorithms needing exit events. Test a path longer than the language recursion limit, a disconnected graph, a self-loop, and adjacency orders with multiple branches. Verify both entry and finish sequences, because an implementation may visit all vertices yet unwind them incorrectly.

Frames remember the next neighbor
Exit time occurs after all descendants
Traversal coverage alone does not prove correct unwinding