## Visually Explained Algorithms

There are three types of depth first binary tree traversals:

• Pre-order: <root><left><right>
• In-order: <left><root><right>
• Post-order: <left><right><root>

We will be focusing on the In-Order Binary Tree Traversal. We can see that starting from the root node, we’ll visit all the nodes in the left subtree, come back to the root node and then visit all the vertices in the right subtree.

Next to each node, we’ll put a couple of reminders for ourselves:

• left subtree
• visit/print node
• right subtree
We’ll begin with the root node.

At this point, we can cross out the left subtree label and start moving down the left subtree.

Since vertex B also has a left subtree, according to the rules outlined by in-order traversal (<left><root><right>), we must visit its left subtree next. So, we cross out the left subtree label on vertex B and move to vertex D.

Vertex D also has a left subtree, so we visit its left subtree next. We cross out the left subtree label on vertex D and move to vertex H.

We can quickly see that vertex H does not have any other left subtrees. We can safely cross that out.

An attempt is made to visit node H’s right subtree, but vertex H has no right subtree. The right subtree label is crossed out and we return to node D. We are now visiting node D after visiting its left subtree. We can add node D to the output.

We move to node D’s right subtree. Node D only has one node in its right subtree, node I.

We can quickly see that vertex I does not have any other left subtrees. We can safely cross that out.

An attempt is made to visit node I’s right subtree, but vertex I has no right subtree. The right subtree label is crossed out and we return to node D.

We’re done with node D’s right subtree, so we return to B. We are now visiting node B after visiting its left subtree. We can add node B to the output.

We move to node B’s right subtree. Node B only has one node in its right subtree, node E.

We attempt to visit node E’s left subtree, but it doesn’t have a left subtree. Once we cross out the left subtree label, we visit vertex E and print out its value.

We attempt to visit node E’s right subtree, but it does not have one. We return to vertex B.

We’re done with B’s right subtree, so we return to node A. Since we’re visiting node A after visiting its left subtree, we will add node A to the output.

We next visit node A’s right subtree.

According to the algorithm, we have to visit node C’s left subtree first.

Since node F does not have a left subtree, we return to node F and print out its value.

Node F does not have a right subtree, so we return to node C. Since we’re returning to node C after visiting its left subtree, we add node C to the output.

The algorithm calls for us to visit node C’s right subtree next.

An attempt is made to visit node G’s left subtree. Since node G has no left subtree, we return to node G and print it out.

We attempt to visit G’s right subtree, but it has none, so we return to node C.

We’re done with node C’s right subtree, so we return to node A.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.