# 100Days of Code #Day 2

I used to be scared of using hierarchical data structures just because they are complex. But the real reason is that we don’t see such complex applications often. Most of us even don’t use Trees in their development day to day. But it in reality our fears got the better of us. We don’t even think of another solution which might be optimal if we use a tree or graph.

This is not a problem at least one we can fix. We have to just familiarize with the problem and concepts more such that we get to open doors to the uncertain domains.

**Breadth First Search:**

As per definition, Breadth First Search or Level order traversal traverses all the nodes connected to root at current level before moving on to the next.

Traversing the tree in level order would produce the following result.

1,2,3,4,5 ( traversing 2 and 3 before going to the next level )

The main application of BFS can be realized in finding the shortest path across tree or graph. Not only trees and graphs, some traversals in matrix can also be optimized using Breadth first traversal.

For eg:

To identify the shortest path at every level we can use breadth first search to go through the array and select the nodes only accessible to itself at each level move on to reach the end of the matrix.

The common logic to implement breadth first search is to use Queue. We first enqueue the root node or the initial element. Then in each round, we process the nodes which are already in the queue one by one and add all their neighbors to the queue. It is to be noted that the newly added elements are not processed until the next round.

Today we are considering the above shortest path problem in a binary matrix question

Given an `n x n`

binary matrix `grid`

, return *the length of the shortest **clear path** in the matrix*. If there is no clear path, return `-1`

.

A **clear path** in a binary matrix is a path from the **top-left** cell (i.e., `(0, 0)`

) to the **bottom-right** cell (i.e., `(n - 1, n - 1)`

) such that:

- All the visited cells of the path are
`0`

. - All the adjacent cells of the path are
**8-directionally**connected (i.e., they are different and they share an edge or a corner).

The **length of a clear path** is the number of visited cells of this path.

**Example 1:**

**Input:** grid = [[0,1],[1,0]]

**Output:** 2

reference : https://leetcode.com/problems/shortest-path-in-binary-matrix/

Algorithm :

- The starting and ending element must not be 1 so ensuring the edge cases starting from the initial index
- Check all its possible neighbors (in all directions) if any of them is zero add it to the queue and increase the index’s distance by one.
- return upon arriving at the destination.

#100DaysofCode #challenge