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

Ok, now we have a very simple class to make a binary tree structure and we can easily represent a tree with it, now what? well, now we are going to learn about the different ways to *traverse* such tree, or well, *visit* all the nodes in the tree. While this is not a complex operation before thinking about implementing it we have to think about *what order* do we want to go through all the nodes. Generally speaking there are two kind of traverse operations: *depth first* and *breadth first* traversal, both operations will traverse from top to bottom.

### Depth-first traversal

In this mode we go from the root node and go and far as we can in each of their *branches* (or children). Depending on the order where the root node is visited we have three different types of depth-first traversal (the code is a method of the `Node`

class we created in the binary tree blog post):

**Pre-order**: root is visited first, then the left node and right node, in the example will be`A, B, D, E, G, H, C, F`

```
fun preOrder(operation: (T) -> Unit) {
operation(data)
left?.preOrder(operation)
right?.preOrder(operation)
}
```

**In-order**: left child first, then root and right node, in the example tree will be`D, B, G, E, H, A, C, F`

```
fun inOrder(operation: (T) -> Unit) {
left?.inOrder(operation)
operation(data)
right?.inOrder(operation)
}
```

**Post-order**: left child first, then right and root node at the end, in our tree will be`D, G, H, E, B, F, C, A`

```
fun postOrder(operation: (T) -> Unit) {
left?.postOrder(operation)
right?.postOrder(operation)
operation(data)
}
```

You could create your own depth first traversal variations, for example, visiting right before left, the important thing here to remember is how the nodes are visited, this affects a lot the operations you will do in tree nodes (as you see in the order), one good example of different usages of each depth-first traversal is in expression evaluations.

The simple test bed for our operations is this (using the tree in the illustration and the cases we already discussed):

```
class TreeTraverseTests {
private val root = Node('a',
Node('b',
Node('d'),
Node('e',
Node('g'),
Node('h')
)
),
Node('c', right = Node('f'))
)
@Test
fun `pre-order traverse`() {
val result = mutableListOf<Char>()
root.preOrder { result.add(it) }
assertEquals(listOf('a', 'b', 'd', 'e', 'g', 'h', 'c', 'f'), result)
}
@Test
fun `in-order traverse`() {
val result = mutableListOf<Char>()
root.inOrder { result.add(it) }
assertEquals(listOf('d', 'b', 'g', 'e', 'h', 'a', 'c', 'f'), result)
}
@Test
fun `post-order traverse`() {
val result = mutableListOf<Char>()
root.postOrder { result.add(it) }
assertEquals(listOf('d', 'g', 'h', 'e', 'b', 'f', 'c', 'a'), result)
}
}
```