# Depth First Search

## Nodes are on same path in a tree or Not

Problem Statement Given a tree and two nodes of tree and the task to check whether these two nodes are on the same path from root to the bottom or not. Example Input Node1 = 1 Node2 = 5 Expected Output Yes Approach The idea is to apply Depth First Search on every node. And Nodes are on same path in a tree or Not

## Count number of trees in a forest

Problem Statement Given a forest with edge representation, find the number of trees in the forest. Example Input edges = {{0, 1}, {0, 2}, {3, 4}, {4, 5}, {5, 6}} Expected Output 2 Approach The idea is to apply Depth First Search on every node. If every connected node is visited from one source then Count number of trees in a forest

## Detect Cycle in a Directed Graph

Problem Statement Given the directed, connected and unweighted graph G and the task to check whether the graph contains a cycle or not. Example Input Expected Output No Approach The approach is to use Depth First Traversal to detect a cycle in a Graph. While traversing through the graph if previous node visited node is encountered again Detect Cycle in a Directed Graph

## Depth First Traversal for a Graph

Depth First Search (BFS) is a recursive graph traversal algorithm that is used to traverse all the vertices of a graph in a depthward motion. In other words, it starts the graph traversal from root node and explores all the branches. Example of Depth First Traversal for a Graph Depth First Traversal is used to traverse all the vertices of Depth First Traversal for a Graph

## Number of Islands

Given a 2D grid consisting of either ‘1’ or ‘0’ character at each position. ‘1’ represents land and ‘0’ represents water. An island is a mass of land which is surrounded by water. Count the number of islands. . Example Test Cases Sample Test Case 1 Input grid: 11110 11010 11000 00000 Expected Output: 1 Number of Islands

[gravityforms id="5" description="false" titla="false" ajax="true"]