Guidelines

First of all you should remember that you can look at matrix/grid and trees just as a specilization of graphs. Tree is a connected acyclic undirected graph (connected == there is path between any pair of nodes, acyclic = no cycle in the graph, undirected = the direction of relation is not important e.g. child is connected to parent just like the parent is connected to the child in tree). For the BFS purposes matrix/grid can be looked as 4-directionally adjacent graph, any matrix cell is a node in graph and it's connected to the 4 cells above, below, left and right. So if you get a tree or matrix/grid shortest path or level traversal problem remember to think about them as graph and apply the BFS.

You will need BFS in two scenarios:

• Find the shortest path between two graph elements
• Level by level traversal in parent-child tree like structures (same logic can be applied to topological sort in graphs)

Template that can be used for grid/matrix problems asking for shortest path:

Java

int[][] directions  = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }}; // down, right, up, left
Queue<int[]> q = new LinkedList<>();
int level = 0;

// put initial candidates in the queue
q.add(new int[]{i, j});

while(!q.isEmpty()){
    int size = q.size();
    while(size-->0){ // loop over the current level
        int[] current = q.poll();
        for(int[] d: directions){
            // initialize new candidate
            int newRow = current[0] + d[0];
            int newCol = current[1] + d[1];

            // check boundary
            if(newRow < 0 || newRow >= mat.length || newCol < 0 || newCol >= mat[0].length || grid[newRow][newCol] != 1) continue; // checking the boundary

            // perfom calculation and add the next level candidates
            q.add(new int[]{newRow, newCol});
        }
    }
    ++level;
}

JavaScript

const directions = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
]; // down, right, up, left
const q = [];
let level = 0;

// put initial candidates in the queue
q.push([i, j]);

while (q.length > 0) {
  let size = q.length;
  while (size-- > 0) {
    // loop over the current level
    const current = q.shift();
    for (const d of directions) {
      // initialize new candidate
      const newRow = current[0] + d[0];
      const newCol = current[1] + d[1];

      // check boundary
      if (
        newRow < 0 ||
        newRow >= mat.length ||
        newCol < 0 ||
        newCol >= mat[0].length ||
        grid[newRow][newCol] !== 1
      )
        continue;

      // perform calculation and add the next level candidates
      q.push([newRow, newCol]);
    }
  }
  level++;
}

Python

directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # down, right, up, left
q = []
level = 0

# put initial candidates in the queue
q.append([i, j])

while len(q) > 0:
    size = len(q)
    while size > 0:  # loop over the current level
        current = q.pop(0)
        for d in directions:
            # initialize new candidate
            newRow = current[0] + d[0]
            newCol = current[1] + d[1]

            # check boundary
            if newRow < 0 or newRow >= len(mat) or newCol < 0 or newCol >= len(mat[0]) or grid[newRow][newCol] != 1:
                continue

            # perform calculation and add the next level candidates
            q.append([newRow, newCol])
        size -= 1
    level += 1

C++

vector<vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // down, right, up, left
queue<vector<int>> q;
int level = 0;

// put initial candidates in the queue
q.push({i, j});

while (!q.empty()) {
    int size = q.size();
    while (size-- > 0) { // loop over the current level
        vector<int> current = q.front();
        q.pop();
        for (const auto& d : directions) {
            // initialize new candidate
            int newRow = current[0] + d[0];
            int newCol = current[1] + d[1];

            // check boundary
            if (newRow < 0 || newRow >= mat.size() || newCol < 0 || newCol >= mat[0].size() || grid[newRow][newCol] != 1) {
                continue;
            }

            // perform calculation and add the next level candidates
            q.push({newRow, newCol});
        }
    }
    ++level;
}

Same goes for graph and tree, we're just changing the directions and boundary checking. For tree we can have root.left and root.right (only two direction for binary trees) and for graphs we have adjacency list for each node. For boundary checking for tree we can check if the left and right child exist and for graph we can check if we already visited the node. Directions are more generalize in graph, and you can have all sort of connections between nodes depending on the problem definition (good example is diffbyone where two words have a connection if the differ only be one letter like we have in the Word Ladder).