After Intro to Graph Algorithms – BFS & DFS, let’s take a look at some popular and most common interview questions. Questions that fall under this category are quite typical and static, so it’s not difficult to master them if you go through the following lists, and then you will find patterns in their solutions.
The steps for using BFS and DFS are straightforward – construct a graph G=(V+E) first and then start exploring. So this post will list the BFS and DFS questions that are highly recommended for practicing. In the next post, [Leetcode for Interview]DFS, BFS, and Backtracking II – How to backtrack? Detailed Explanations with Examples, we will talk about how to implement DFS with pruning – Backtracking.
Notably, since BFS and DFS would literally exhaust every possible path in the graph, sometimes it might not be as efficient as other algorithms such as Dynamic Programming and Greedy Algorithms etc..
Breadth-First-Search
- 103. Binary Tree Zigzag Level Order Traversal – Medium
- 127. Word Ladder – Medium
- 199 Binary Tree Right Side View – Medium
- 200. Number of Islands – Medium
- 210. Course Schedule II – Medium
- 314. Binary Tree Vertical Order Traversal – Medium
- 513. Find Bottom Left Tree Value – Medium
- 773. Sliding Puzzle – Hard
- 994. Rotting Oranges – Medium
Depth-First-Search
- 98. Validate Binary Search Tree – Medium
- 101. Symmetric Tree – Easy
- 104. Maximum Depth of Binary Tree – Easy
- 105. Construct Binary Tree from Preorder and Inorder Traversal – Medium
- 106. Construct Binary Tree from Inorder and Postorder Traversal – Medium
- 109. Convert Sorted List to Binary Search Tree – Medium
- 110. Balanced Binary Tree – Easy
- 111. Minimum Depth of Binary Tree – Easy
- 114. Flatten Binary Tree to Linked List – Medium
- 124. Binary Tree Maximum Path Sum – Hard
- 200. Number of Islands – Medium
- 257. Binary Tree Paths – Easy
- 323. Number of Connected Components in an Undirected Graph – Medium
- 337. House Robber III – Medium
- 394. Decode String – Medium
- 547. Friend Circles – Medium
- 695. Max Area of Island – Medium
- 733. Flood Fill – Easy
- 785. Is Graph Bipartite? – Medium
- 886. Possible Bipartition – Medium