## Introduction

**Prerequisites**: Recursion, Queue

A breadth first search is a search that traverses level by level. For example, in a tree, the search will transverse everything from the first layer, to the second layer, the third layer and all the way down to the last layer. BFS is implemented with a queue.

- Push the root into the queue.
- Pop the first element from the queue and push its non-visited neighbours.
- Repeat 2 until the queue is empty.

## Implementation

Printing a binary tree using BFS:

void bfs(Node root) { Queue<Node> q = new Queue<Node>(); q.push(root); while (q.isEmpty() == false) { Node cur = q.pop(); System.out.println(cur.value); if (cur.left) { q.push(cur.left); } if (cur.right) { q.push(cur.right); } } }

## Exercises

- Given a grid of squares with walls at certain locations and two locations A and B, find the minimum distance (going up/left/right/down) between the locations or impossible otherwise. For example if A is at (1,1) and B is at (3,1) but there is a wall at (2,1) then the minimum distance would be 4 (down, left, left, up).
- Given a tree of letters (A is the root), output the tree using BFS with separators between levels:
- Example: A→B, B→D,B→C, C->G will output A | B | C D | G.

- Given a tree of letters, and two letters X and Y determine if X is an ancestor of Y or if Y is a ancestor of X or neither. X is an ancestor of Y if X's subtrees contain Y.
- Example: A→B, B→C, B→D, D→G, A is a parent of both C and D but G and C are not ancestors of each other

- Given a binary tree and a node in the binary tree, find the next node in BFS order of the tree.