Pre-order Traversal: Root, Left, Right!

  • Explain pre-order traversal.

This is the strategy for pre-order traversal:

For every node, visit it, then visit its left subtree, then visit its right subtree.

Following the strategy above will generate this sequence:

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

Explanation

We start with the root, $9$; then we visit all the nodes in its left subtree. So we move to the subtree rooted at $5$. Next, we visit $5$; then we visit all the nodes in its left subtree. So, we move to $2$. First, we visit $2$, and then we visit all the nodes in its left subtree. But $2$ has no subtree to its left. So we move to visit all the nodes in the right subtree of $2$.

So we move to node $4$. We visit $4$. Then, we must visit all the nodes in the subtree to the left of $4$, but there is none. So, we 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 now move to the right subtree of $5$ and $\dots$

Here is a recursive definition of pre-order traversal: for each node, visit it, then recursively perform pre-order traversal of its children (the subtrees rooted at its left and right child, in that order).

Resources