You will probably want to refer to Figure 5.49 of the text during this discussion.  This figure shows the five legal trees
obtained by permuting three nodes.  Problem 3.1 gave the formula for determining the number of permutations, and, hence, the number of distinct binary trees.  Here we'll just elaborate by examining the trees appearing in Figure 5.49.

As the figure shows, the PreOrder traversal is always 1,2,3.  However, the InOrder traversals vary widely.  These traversals
are, from left to right: 123, 132, 213, 231, 321. We can easily reproduce these results by using the railtrack analogy discussed
in problem 3.1.  Let me indicate how each of the InOrder traversals was obtained using this analogy.

Tree 1:  Each number is added to the stack and then removed from
the stack.  The stack contains no more than one element at any
given time.

Tree 2:  The first number is added to, and removed from, the stack.  We then add the remaining two numbers as a unit, and
remove each of them.

Tree 3: The first two numbers are added to the stack as a unit.  Both numbers are removed before the last number is added.

Tree 4:  The first two numbers are added to the stack.  Only the second number is removed.  The third number is added to the stack,  and the remaining two numbers are removed.

Tree 5:  The three numbers are added to the stack as a unit.  They are then removed individually.

Because the traversals follow the stack's operations certain combinations are illegal.  For example, it is impossible to arrive
at the combination 312.  Why?  Because there is no way we could remove three from the stack followed by a one.