ErasedSoul
Back to blog
•
3 min read
DFS Patterns

Patterns

1. Flood Fill

Using a visited array

2. Cycle Detection using DFS

Using 3 step/3 coloring technique.

0 -> Not Visited 1 -> Visiting 2 -> Done.

3. Connected Components

A connected component is a maximal set of connected nodes in an undirected graph. In other words, two nodes are in the same connected component if and only if they can reach each other via edges in the graph.

  1. Building Roads

1. Number of Islands

Normal DFS to count connected components

2. Number of Distinct Islands

A way to identify the structure. Using L,R,U,D and B as Backtracking and S can be used as Start

3. All paths from source to target

DFS + Backtracking.

Time complexity is Important:

There are (n-2) intermediate nodes, which can either be include/no included in the path, So 2^(n-2).

Also in worst case each path with take O(n) to copy in answer array.

So, total Time complexity = O((2^n) * n)

4. Cloning a graph

To clone a graph we need a ==HashMap<Node,Node> (a mapping from original to new)==

Complexity

Time: O(V + E) we go through all the vertices and examine all the edges

Auxiliary Space: O(V) as the recursion stack can go up to V in worst case when the graph is a long chain.

We don’t have to consider the output space Output Space: O(V + E) as we create N nodes the total size of the adjacency matrix in every node is O(E).

5. Bipartite check

Using DFS we try to 2-color the graph. If any adjacent neighbor contains the same color as the current node, then the graph is not bipartate.

NOTE: Where are tend to make mistake is not running dfs on every node as the graph can be disconnected.

Complexity

Time: O(V + E) We visit all nodes and examine all the edges.

Space: O(V) as the recursion stack depth can go upto V in worst case when the graph is a long chain.

6. All Nodes Distance k from the target node in Binary Tree

Only root and target node is given. We cannot start bfs from target node ans adj list not provided.

We need to do this using dfs only.

Type of answer nodes ->

  1. In the subtree of targetNode
  2. Node where targetNode is on the left subtree and we need to find all the nodes on the right subtree and vice versa.
  3. The above also include the node whose subtree needs to be checked.
Complexity

Time: Each node can be visited atmost 2 times so time complexity is O(n)

Space: O(h) for the recursion stack.