In-order Traversal: Left, Root, Right!

  • Explain in-order traversal.

In a BST, an in-order traversal will visit nodes according to their natural ordering.

This is the strategy:

To perform an in-order traversal of a subtree rooted at a given node, first (recursively) traverse the nodes's left subtree, then visit the given node, then (recursively) traverse the nodes's 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 is 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 now 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