Traversal Generation

In this section, we examine different ways of generating trees. Since we've just gone over traversals, we begin by considering how we might generate a tree using the traversal methods.

The idea behind traversal generation can be thought of as "working backwards:" If we're given traversal sequences, we can generate the tree that results in those sequences. Note the plural — traversal sequences . This is a key point, because with just a single traversal sequence, we do not have enough data to generate a tree. For example, suppose we're told that the following is a preorder traversal sequence of the tree's node values:

Without further information, we cannot construct a tree because the traversal sequence above could have come from five possible trees:

Accordingly, preorder, inorder, and postorder sequences alone are insufficient. We need additional sequences. Specifically, we need one of the following combinations of data:

1. The preorder sequence and inorder sequence, or
2. the postorder sequence and inorder sequence.

Notice that in both cases, we need the inorder sequence. To see why we need the inorder sequence, let's just go straight to the algorithm with an example.

First, we're given two sequences. A preorder traversal sequence:

and an inorder traversal sequence:

From the preorder sequence, we know that the node containing 4 is the root. Thus, the tree's root is a node containing 4. Then, from the inorder sequence of the tree, we know that all the values to the left of 4 form the left-subtree, and all the values to the right of 4 form the right-subtree. Thus, we have:

The rest of the algorithm follows this basic step. We continue splitting until there's nothing left to split. So, we look at the next element in the preorder sequence and see that it's 7. This tells us that the node containing 7 is the root of the left-subtree.

We go to the inorder sequence and look for 7, and find that it's the first element. Inorder sequence then tells us that everything to the left of 7 forms its left-subtree, and everything to the right forms the right-subtree. Thus, we have:

The algorithm continues. We go to the next element, and see that it's 9. We go to the inorder sequence, look for 9, and divide accordingly:

We then move to the next element in the preorder sequence, 6. Here, we see that it's a single element — there's nothing to its left or right. The same goes for 3. So we go the next element, 2. Again we search for 2 in the inorder sequence, and find that it has 5 and 8 to its left, and 1 to its right:

At this point, the algorithm should be clear. Executing the rest of the algorithm, we get: