# How to write a bfs without Array.shift() in Javascript

Do you do coding interviews with Javascript?

Then you may have come across this question: **How can we write breadth-first search in Javascript without the Array.shift() function?**

Why do we care? Because `Array.shift()`

takes `O(N)`

time.

## Generic BFS logic

Here is the generic logic for BFS, from Wikipedia:

```
1 procedure BFS(G, root) is
2 let Q be a queue
3 label root as explored
4 Q.enqueue(root)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as explored then
11 label w as explored
12 Q.enqueue(w)
```

## Problem with Javascript BFS with `Array.shift()`

Here’s the problem doing it with Javascript

```
function bfs(root, adjacencyList) {
if (!root) return
const queue = [root]
const visited = new Set()
while (queue.size) {
const node = queue.shift() // <--- takes O(N) time!! So the entire BFS takes O(N^2)
const neighbors = adjacencyList.has(node) ? adjacencyList.get(node) : []
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
queue.push(neighbor)
}
}
}
}
```

## How to write BFS in JS without `Array.shift()`

Use a Set.

Why? A `Set`

keeps the insertion ordering. It’s pretty much a queue.

⚠ Limitationthis only works with primitive values and object references, due to Set’s equality comparator. Hopefully things change with the Record/Tuple proposal

Here’s our BFS:

```
function bfs(root, adjacencyList) {
if (!root) return
const queue = new Set([root])
const visited = new Set()
while (queue.size) {
let currentNode for (const node of queue) { currentNode = node break } queue.delete(node)
const neighbors = adjacencyList.has(node) ? adjacencyList.get(node) : []
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
queue.push(neighbor)
}
}
}
}
```

That’s all. Hope this helps!