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

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:

1. `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}`.

1. `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 }`.

1. `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 + " ")
}
}
``````

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 */
if n != nil {
s := []*node{n}
for len(s) > 0 {
current_node := s
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.