Trees and Traversal Basics

 Trees are a special kind of graph—one of the most common data structures you’ll ever come across. The requirements to be a tree are quite straightforward: one single component, no cycles, and a clear sense of directional hierarchy, but in which movement is allowed in both directions through that hierarchy: up and down.

A tree has exactly one “root” node. In plain English, the root is the source, and everything branches out from it. We’ll need some more terms to create a more rigorous definition. If X is connected to Y, and the path from the root to X is shorter than the path from the root to Y, then X is the “parent” of Y, and Y is the “child” of X. Because trees cannot have cycles, a node has exactly one parent but may have several children. I will leave it as an exercise for the reader to prove to yourself that the way trees are defined guarantees that from the root to any given node, the path will always be unique.

One of the most common trees you’ll see is the binary tree. (“Binary,” as with the related search algorithm, does not mean 1100010101001, but “splitting things in half,” or, in this case, “no more than 2 children.”) A node that has no children is called a leaf.

Moving through a tree—to read its values or to do something with it—is called “traversing” it, and any set of all the nodes which traverses a tree is a “traversal.” To explain these, let’s stick with a binary tree, which, naturally, has a root, a left half, and a right half.

There are many common types of traversal:

• Level-order
• In-order
• Pre-order
• Post-order

Let’s move one by one, starting with a level-order traversal of this tree:



In a level-order traversal, we start at the root, then move down to the next level and read off left to right, then the next level, then the next level, and so on. A level-order traversal of this tree would read 5, 12, 13, 7, 14, 2, 17, 23, 27, 3, 8, 11.

Now let’s look at in-order, the first recursive traversal. In plain English, traverse the left, traverse the root, traverse the right.  

Let’s now look at this tree:

To traverse this in-order, we look at the left side first, then the root, then the right.
The root is 2, and it’s left child is 5. 5 becomes the new “root” of a smaller subset of the original tree, which we call a “subtree” of the original.  But 5 is now treated as a root, and the order is left-root-right, so we go left again, and we hit a leaf. (Therefore, this process is recursive.) So we traverse the left subtree as 6, 5, 7. Then we come back up to the “real” root, and get the 2. The same process occurs in the right subtree: the subtree’s root is 10, so the left side, 20, comes first, then the 10, then the 30. So, put together, the whole in-order traversal of this tree would look like 6, 5, 7, 2, 20, 10, 30. Notice the recursive nature of this algorithm, and how innately recursive trees really are. Awareness of this fact now will serve you well when looking at pre- and post-order.

To look at pre-order, we can, in fact, use the same tree. (This will be good for you, because you can then see an apples-to-apples comparison of different traversals on the same tree.) Pre-order moves in the order “root, left, right.” Therefore, the order is: 2, left subtree recursively (5, 6, 7), right subtree recursively (10, 20, 30)—giving us a complete traversal of 2, 5, 6, 7, 10, 20, 30.

Finally, post-order is also recursive, and, again, using the same tree gives us the benefit of the comparison. Post-order processes the root last, so it moves through the left and right subtrees first. The root of the whole is the 2, and the left subtree is rooted at 5, and the right rooted at 10.  The traversal of the left subtree then is 6, 7, 5; the right subtree is 20, 30, 10; and the root is 2. Thefore, the whole postorder traversal is 6, 7, 5, 20, 30, 10, 2.