So far we've talked quite a bit about the tree data structure. Including how to create a tree, add to it, search for an element, and how to properly delete nodes. In this guide we're going to discuss the various ways that you can traverse through a tree.

What is Tree Traversal?

I like the term traversal. When I think of the word images fill my find of traversing up a steep mountain pass or traversing through the forrest. No matter how you like to think of traversal there should be one common thread: being a journey. And this same definition works in the world of data structures.

For the tree data structure, tree traversal is the process of visiting each node on the graph.

If you remember, trees are a type of the Graph data structure. Therefore the concept of traversal will apply to both trees and graphs.

Tree Traversal Types

When it comes to traversing trees there are three processes to be aware of:

• In order
• Post order
• Pre order

Each of these traversal types will generate a different set of results, so it's key to understand which one is the best fit for your algorithm.

For this case study we're going to utilize a binary search tree with the values of:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

In order traversal

I started with in order traversal because it's the most straightforward approach. They call it in order from a reason, and the reason is that the nodes will be visited... in order.

So when you have an algorithm that traverses all of the nodes on a tree and you need to have the values returned in sorted order, this is the approach you will want to go with. The result of traversing the tree with the in order algorithm will result in returning the following values:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Pre order traversal

If you've never witnessed the pre order traversal process in action before it may look a little odd. When I first learned this approach it took me a few times running through it before it started to make sense.

The first key to remember for pre-order traversal is that you always start with the root node. So for our case study we will begin our journey at the 6 node. From there we'll make a beeline to the left, so the next node will be 3, followed by 2, and lastly 1.

Once we have reached the lowest value in the tree we will visit the node that takes the fewest hops, in this case it would be the 4 node.

If 4 had any child nodes we would visit them, however since it's simply a leaf we will cross over to the right side of the tree and visit the node that is the closest from a hop perspective. In this case the node would be 8.

Are you starting to see the trend? This is a recursive algorithm, which means that we will follow the same process for the rest of the tree. I highly recommend that you try to finish the traversal process before looking at the full solution below.

Following with the pre order traversal process, the full route our algorithm will take is going to be:

6, 3, 2, 1, 4, 8, 7, 5, 10, 9

There are three keys for understanding how to utilize the pre order traversal process:

1. Start at the root node and travel all the way to the left most value.
2. Visit the closest node on the tree. And in this case closest means the node that it would take the fewest number of hops to reach.
3. Recursively repeat this process until the each node on the tree has been visited.

Post order traversal

Last on the list of the ways that we can take a journey through a tree data structure is post order traversal. The post order process is relatively straightforward if you imagine that you're picking fruit off a real life tree.

Have you ever heard the phrase "low hanging fruit"? You can think of the post order process as picking low hanging from from a tree data structure. This doesn't mean picking the lowest values first. Remember that picking the lowest values is what we do with the in order process.

Instead post order means that you take all of the leaves off the tree first and ignore the roots (aka parent nodes) until they have become leaves. If that seems a little fuzzy, I think this visual will clear things up.

For the post order traversal we will start with the lowest value node, which in this case is 1. From there we move onto the next lowest value leaf on the tree, which is 2. From here we visit the 4 node, and after it we will move to the 3 node. Notice how this is not in value order, but instead it gives a priority to leaves over roots.

From this point the algorithm will pick the leaf with the lowest value, which is 5, and this process will continue until each node has been visited. The final route for this traversal process will be:

1, 2, 4, 3, 5, 9, 7, 10, 8, 6

What's the Point?

If you're like me (#practical), your first thought may be:

"When in the world will I ever use these traversal processes?!"

It's a fair question. And to be 100% honest, I didn't start using any of these concepts until I started building programs that utilized Graph based algorithms. However if you don't have a firm understanding for how to traverse trees you will discover that you'll be lost in the world of graphs. So for right now my recommendation is to focus on these and keep the mindset that these are foundational principles. And that you will need to understand how they work in order to move onto more complex algorithms.

If you find the concept of having to learn theoretical concepts annoying (like I did when I was teaching myself programming), I find it helpful to take a different perspective. Imagine back to when you were first learning about loops. You probably started by looping over a basic data structure like an array, like this:

arr = [1, 2, 3, 4, 5]

arr.each do |i|
  p i
end

# 1 2 3 4 5

But wait! What's the point in printing out 5 integers? It seems a bit pointless (kind of like traversing through a tree). However by learning this looping mechanism you were able to move onto concepts such as printing out a set of records from a database, which is something you probably utilize daily.

In the same way, a number of these high level concepts are giving you foundational knowledge that you will be able to use in real world development. There is a reason why the tree data structure is one of the most popular topics that interviewers like to talk about during development job interviews. If you have a solid understanding of the tree data structure you will be able to work with more complex algorithms and data structures later on.