DFS

3 problems using this pattern

About this pattern:

Depth-first search for exploring all paths in trees and graphs recursively.

Often used with: Recursion Tree Graph Union Find

Complexity Range

Time Complexity


                  O(n)

(2 problems)


                  O(V + E)

(1 problem)

Space Complexity


                  O(h)

(2 problems)


                  O(V)

(1 problem)

Problems Using DFS

Maximum Depth of Binary Tree

Return the maximum depth of the binary tree.

Example: [3,9,20,null,null,15,7] → 3

Tree DFS Recursion

View Solution →

Same Tree

Check if two binary trees are the same.

Example: p = [1,2,3], q = [1,2,3] → true

Tree DFS Recursion

View Solution →

Number of Connected Components

Count connected components using DFS traversal.

Medium LeetCode

Time: O(V + E)

Example: n=5, edges=[[0,1],[1,2],[3,4]] → 2

Graph DFS Union Find

View Solution →

← Back to All Patterns

View All Categories