## 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.

1. Push the root into the queue.
2. Pop the first element from the queue and push its non-visited neighbours.
3. 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

1. 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).
2. 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.
3. 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
4. Given a binary tree and a node in the binary tree, find the next node in BFS order of the tree.