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 9, 5, 2, 4, 7, 8, 17, 12, 14, 21, 20, 25

Explanation

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

So we move to node 44. We visit 44. Then, we must visit all the nodes in the subtree to the left of 44, but there is none. So, we visit all the nodes to the right subtree of 44, but there are none. Therefore, we conclude our visit of all the nodes in the right subtree of 22, and by proxy, our visit to all the nodes in the left subtree of 55 is done too. We must now move to the right subtree of 55 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