## Data structures, Binary trees, breadth-first traversal

We have not finished with trees yet! oh no! trees are one of the most versatil data structures out there in the wild. Last time we were taking a look at how to *visit* or *traverse* all the nodes in a tree and we saw depth-first traversal, but what if we want to visit *the same tree* as last time but from top to bottom and left to right? (in this case generating the order `A, B, C, D, E, F, G, H`

). Well, this type of traversal is named *breadth-first traversal* or *level order* traversal.

The easiest way to implement a level order traversal is using an additional data structure, a queue. The idea is simple, we start from the root and then add left and right to a queue and pops the queue until no element is present, nothing really exotic here:

```
fun levelOrder(operation: (T) -> Unit) {
val queue = Queue<Node<T>>()
queue.add(this)
while (!queue.isEmpty()) {
val elem = queue.pop()
operation(elem.data)
elem.left?.let { queue.push(it) }
elem.right?.let { queue.push(it) }
}
}
```

As previous blog post we add this method to the `Node`

class. Notice the usage of a `Queue`

structure, you can use the one implemented in the simple queue blog post. As with depth-first traversal there could be variations of the order you visit the nodes but in general it will be always from top to bottom and left to right.

This is easily tested with this simple method (you can add it to the previous unit tests for tree traversal):

```
@Test
fun `lever-order traverse`() {
val result = mutableListOf<Char>()
root.levelOrder { result.add(it) }
assertEquals(listOf('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), result)
}
```

A very useful usage of breath-first traversal is converting a tree into a linear structure, like an array, pretty much in the same way we are testing the traversal in our tests.