M

                       /   \

                      G     R

                     / \   / \ 

                    E   L P   X

                           \

                            Q

PreOrder: M G E L R P Q X

InOrder : E G L M P Q R X

To create the tree, we process the sequences from the first character to the last character.  For the PreOrder sequence, each time that we place a value into the tree, we get a new PreOrder value.  For example, we know that M is the root of the tree.  place it in the tree and get the next character in the PreOrder sequence. 

For the InOrder sequence, we get a new character only if the current character matches the current PreOrder character, or the current character matches a value in the tree.

Continuing with our example, we next compare G, from the PreOrder sequence, and E, from the InOrder sequence.  Since they don't match, we know that G is a left child of M.  We then compare E and E.  Because they match, we have obtained two pieces of information:

1. we know that E is the left child of G, and

2. we know that it is a leaf node.  We now back up to E's parent, and continue by comparing L and L.  They   match which means that L is a right child of G.  We again backup, but this time to the root node.  Since R and P don't match, R is a non-terminal right child of M. Traversal continues with R's left child.  Notice that the next two characters in each sequence match.  The first character (P) is obviously the left child of R, but can we correctly place the second character (Q).  This character must be a right child because the last character was a left child.  Furthermore, it must be the right child of the newly created left child because the InOrder traversal hasn't yet reached R.  The correct positioning of Q is the key to the creation of a unique tree.  Because we can handle cases where the non-terminal node has only one child, we can create a unique tree.