# Binary Tree Traversal

Overview of Breadth and Depth first traversal in a Binary Tree

02.12.2017

## Overview

There are two main ways to process data within a binary tree. In this post, I go over some breadth-first and depth-first searching algorithms.

Here is a my attempt at a tree, which I will use as an example.

```
F
/ \
D H
/ \ / \
B E G J
```

## Breadth-First Search

In a breadth-first search, the elements of the tree are visited from left to right, and top to bottom, just like reading some text. The example tree would be evaluated as, `{F, D, H, B, E, G, J}`

.

## Depth-First Search

In depth-first search, visiting a child node is visiting a complete subtree. There is more than one way to perform a depth-first search. Some of the most common are as follows:

`root->left->right`

(pre-order DFS traversal)

A pre-order DFS traversal of the example tree above would look like this: `{F, D, B, E, H, G, J}`

.

`left->root->right`

(in-order DFS traversal)

An in-order DFS traversal of the example tree above would look like this: `{B, D, E, F, G, H, J }`

.

`left->right->root`

(post-order DFS traversal)

Finally, a post-order DFS traversal of the example tree above would look like: `{B, E, D, G, J H, F}`

.

## Example: Expression Trees

Just to give these different ways of traversing a binary tree some context, take mathematical expressions as an example. The operators are the leaf nodes, and the operands are the nodes with one or two subtrees.

```
*
/ \
- +
/ \ / \
2 3 7 10
```

When it comes to writing math expressions, there are actually a few different ways to do so. Polish notation, also known as prefix notation, is when the operators are written on the left of the operands (`+ 3 2`

for example.) Similarly, reverse Polish notation is where the operators are written to the right of the operands (`3 2 +`

).

Traversing an expression tree using an in-order DFS algorithm produces an expression like most of us are used to. The above example would come out to be: `(2 - 3) * (7 + 10)`

.

Going through the expression tree using pre-order DFS produces the Polish notation version of the same expression: `* - 2 3 + 7 10`

Finally, a post-order DFS produces the reverse Polish notation: `2 3 - 7 10 + *`

Pretty Neat.

## Depth First Implementation

Now here is some Go code to traverse the binary tree. A node looks like this:

```
type node struct {
value string
left *node
right *node
}
```

And here are the different DFS traversal algorithms:

```
/* pre-oder DFS traversal */
func preorder(n *node) *node {
if n != nil {
fmt.Printf(n.value + " ")
preorder(n.left)
preorder(n.right)
}
return n
}
/* in-oder DFS traversal */
func inorder(n *node) {
if n != nil {
inorder(n.left)
fmt.Printf(n.value + " ")
inorder(n.right)
}
}
/* post-oder DFS traversal */
func postorder(n *node) {
if n != nil {
postorder(n.left)
postorder(n.right)
fmt.Printf(n.value + " ")
}
}
```

## Breadth First Implementation

To traverse a binary tree from top to bottom and right to left, we will need the help of a queue to keep track of the elements that need to be visited next. That’s because any given element in the tree does not have a pointer to any of the other elements on the same level. The algorithm follows this general pattern:

```
enqueue the element.
while the queue is not empty...
dequeue a element
process the element
enqueue the element's left and right children
done
```

Here’s what it might look like in Go:

```
/* breadth first traversal */
func breadth(n *node) {
if n != nil {
s := []*node{n}
for len(s) > 0 {
current_node := s[0]
fmt.Printf(current_node.value + " ")
s = s[1:]
if current_node.left != nil {
s = append(s, current_node.left)
}
if current_node.right != nil {
s = append(s, current_node.right)
}
}
}
}
```

Code from this post can be found here.