Month: April 2014

In-order Traversal of a Binary Tree in C++

In-order traversal is probably the most widely used type of tree traversal algorithm mainly because when applied to Binary Search Trees it can operate on the nodes in order (duh!). The in-order traversal algorithm first operates on the left subtree, returns on the root operates on it and then traverses the right subtree.

To demonstrate the algorithm we’re going to print the integer values of a binary tree whose nodes are described by the following struct:

An unconventional and not very scientific way to think about the algorithm is that it visits nodes in this order:

  1. Left
  2. Middle
  3. Right

It helps if you’re trying to visualize it. Speaking of visualization let’s see an example of the algorithm in action. We have the following binary tree:

binarytree

Starting from root-node 6, the algorithm will check if the node is NULL and since it is not, it will visit its left subtree first, then it will return print 6 and visit the right subtree.

Output so far:

We are at node 9, the start of node-6 left subtree. The node is not NULL so the algorithm goes deeper to the next left subtree

Output so far:

Node 2, also not null. The algorithm goes to the left again

Output so far:

We’ve bumped into NULL, the function returns control to the caller. So we’re back at node 2. We print it

Output so far: 2

Now it’s time for the right subtree. We visit it, find out it’s NULL and then return to node-2. Node-2 is done so back to node-9

Output so far: 2

We’re done with node-9’s left sub tree so we print 9 and head over to its right subtree

Output so far: 2, 9

We’re at node-5, it’s not NULL so we go to its left subtree which is NULL so we return to node-5, print 5 and move to the right subtree which is also non-existent so we go back to node-9

Output so far: 2, 9, 5

We’ve printed node-9’s left subtree, its own value and its right subtree so we’re done and return to node-6. We print 6 and move to the right subtree

Output so far: 2, 9, 5, 6

We are at node-4 which is not NULL so we visit its left sub-tree

Output so far: 2, 9, 5, 6

Node-4’s left subtree does not exist so we return to node-4 and print its value

Output so far: 2, 9, 5, 6, 4

Next, we visit node-4’s right subtree at node-8

Output so far: 2, 9, 5, 6, 4

Node-8 is not NULL so we visit its left subtree. Node-8’s left subtree is NULL so we return to node-8 print its value and visit its right subtree

Output so far: 2, 9, 5, 6, 4, 8

Nothing here so back to node-8. But we’re done with node-8 so back to node-4. Node-4 is also finished, so back to the root. The root is also finished so we’re done.

Final Output: 2, 9, 5, 6, 4, 8

Here’s the code of in-order traversal in C++ :

dimlucas Leave a comment

Pre-order Traversal of a binary-tree in C++

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:

binarytree

 

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.

dimlucas Leave a comment