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:

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++ :