DFS & BFS

May 18, 2021
Algorithms

Introduction

Depth First Search and Breath First Search are extremely common graph traversal algorithms. The main difference is that in BFS visits nodes of the same level one at the same time, whereas DFS follows a node through the rabbit hole until the node no longer has any neighbors to visit. You'll typically perform DFS or BFS when the problem statement has a 2D matrix that requires non-obvious navigation, or a binary tree. There are also other deceptive inputs that initially seem like they require simple array processing or two-pointer processing but can only be answered via DFS/BFS. The example that follows will illustrate this.

An Example

Problem Statement

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

BFS Algorithm

The key to this problem is to realize that we will need to remove a single open or close parentheses from every possible position and check to see if the newly formed string is a valid parentheses. If we go about removing 1 parentheses the first time from all possible positions, then another (which makes a total of two), then another on the third round, we can treat this like a BFS problem.

The code follows below:

BFS solution

The problem can also be solved via DFS. They key thing to remember is that we need to remove the minimum amount of characters until we encounter a valid parentheses. So we need to keep the track of the running minimum value so that our other depth first traversals don't go to deeper levels than the minimum we have encountered. The solution follows below:

DFS Solution

Practice Problems

MEDIUM

Number of Islands

Letter Combinations of a Phone Number

Course Schedule II

Course Schedule

Pacific Atlantic Water Flow

Minesweeper

Populating Next Right Pointers in Each Node II

Construct Binary Tree from Inorder and Postorder Traversal

HARD

Longest Increasing Path in a Matrix

Binary Tree Maximum Path Sum

Remove Invalid Parentheses

Concatenated Words

Recover Binary Search Tree

Related Posts

Stay Updated

Thank you! Your submission has been received!

Oops! Something went wrong while submitting the form