The pre-order traversal algorithm is a traversal algorithm that visits the root node of the tree first, and then recursively visits the left and right subtrees for binary trees, or every other subtree for non-binary ones. In this blog post we’re going to see how the recursive pre-order traversal works. An iterative method is also possible with the use of a stack but I find the recursive method more intuitive, plus if you’re not yet familiar with recursive functions, then recursive tree traversal algorithms is a very nice place to start. To demonstrate the algorithm we are going to print the values of a tree in a pre-order fashion.

Every node in our Binary Tree representation is described by the following struct:

We will be using integers for this example but of course a binary tree may contain whatever data type is needed. You can replace int data with char data or double data, or, even better, use Abstract Data Types and C++ templates. The left and right pointers point to the left and right subtree respectively.

The first thing the algorithm does is to check if the node passed to it is actually a valid node. If it isn’t, the algorithm stops and does nothing more. I know this may sound obvious but it’s vital to understanding the algorithm as you’ll see later in this post.
If the node is an existent one (not NULL) the value of the node gets printed and then the algorithm visits the left subtree followed by the right subtree. Notice that I’m not saying left node but left subtree, so after the root node gets printed the algorithm will visit the left subtree recursively and only after the left subtree has been dealt with, will the algorithm move on to the right subtree. And this is applied recursively to the subtrees of the subtrees and so on.

Ok, enough with theory. Recursive algorithms and especially tree traversal ones are best explained with the use of an example.
Let’s say we want to traverse the following tree:

 

Starting at the node we print the value 6 and then do a pre-order traversal of the left subtree. Only after we’re done with the left subtree will we move to traverse the right one.

Output up until now: 6

The algorithm visits the node with value 9, it’s not null so it prints the value to the output and then traverses the left subtree (the one starting with the value 2)

Output up until now: 6, 9

We’ve reached the node with value 2, the node is not a NULL one so we print the value and move to traverse the left subtree

Output up until now: 6, 9, 2

The left subtree of node 2 is non-existent!. We’ve passed NULL to our algorithm so it will stop. There is nothing more in the left subtree so the algorithm will now visit the right subtree. What subtree? The one on the right of node 2. But that’s non-existent too. So the algorithm is done with the subtree starting at node 2 so it goes back to node 9. The traversal of this node’s left subtree is over so the algorithm will visit its right subtree, namely node 5

Output up until now: 6, 9, 2, 5

Node 5 does not have any child nodes so we’re back at node 6, the root of the tree. Now it’s time to explore the right subtree. The algorithm goes to node 4, prints it and moves to its left subtree

Output up until now: 6, 9, 2, 5, 4

Node 5 does not have a left sub tree, nothing to do here, back to 4. Time to search the right subtree. The root of the right subtree is 8, the algorithm prints it

Output up until now: 6, 9, 2, 5, 4, 8

No left, or right subtree for node 8, back to node 4. We’ve visited both subtrees of node 4, so back to node 6. Same thing here, so we’re done. We’ve traversed the whole tree.

Now let’s see how this translates into code:

As we’ve seen earlier in this post, the algorithm stops if the given root is NULL. If the node is not NULL the algorithm immediately prints the data and then moves on to do the same for the left and right subtree. That’s it! It’s actually simple.

A variation of the algorithm that actually results into a smaller call stack size, checks the left and right subtrees before traversing:

The check for NULL takes place in both algorithms so the second one is a very minor optimization because of the fewer function calls. However the first algorithm seems cleaner and easier for beginners to grasp.