Binary Tree Traversal

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:

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

2. 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 }.

3. 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.