In-order Traversal: Left, Root, Right!

In a BST, in-order traversal will produce the sequence in order (duh!). In a way, we recreate the ordered sequence where this binary (decision) tree was generated from:

This is the strategy:

For every node, visit left subtree, then the node, then right subtree.

Following the strategy above will generate this sequence:

$$ 2, 4, 5, 7, 8, 9, 12, 14, 17, 20, 21, 25 $$

Explanation

We start with the root, $9$, but the strategy demands us to visit all the nodes in the left subtree first. So we move to the subtree rooted at $5$. However, before we visit $5$, we must visit all the nodes in its left subtree. So we move to the subtree rooted at $2$. Since there is no subtree to the left of $2$, we can visit $2$. Thus the first node that we will iterate over is going to be $2$.

According to the strategy, when a node is visited, we must visit all the nodes in its right subtree. So we move to node $4$. We must visit all the nodes in the subtree to the left of $4$ but there are none, so we can process $4$ itself. Therefore, $4$ will be the second node we will iterate over. We must now visit all the nodes to the right subtree of $4$ but there are none. Therefore, we conclude our visit of all the nodes in the right subtree of $2$, and by proxy, our visit to all the nodes in the left subtree of $5$ is done too. We must no process $5$ itself. Thus, $5$ will be the third node we will iterate over. Then we move to the right subtree of $5$ and $\dots$

Here is a recursive definition of in-order traversal: for each node, recursively perform in-order traversal of the subtree rooted at its left child, then visit the root (the note itself), then recursively perform in-order traversal of the subtree rooted at its right child.

Resources