Page 264, Exercise 2


Yes, the InOrder and PostOrder sequences uniquely define a tree.  The key to determining a unique sequence is the ability to
determine the left children from the right children.  For example,  look at the following tree:

                         M

                       /   \

                      G     R

                     / \   / \ 

                    E   L P   X

                           \

                            Q

PostOrder: E L G Q P X R M

  InOrder: E G L M P Q R X

 
To create this tree from the PostOrder and InOrder sequences, we process the sequences from the last to the first
characters. For the PostOrder sequence, each time we place a node in the tree we discard it. For example, we know that M must be the root of the tree because it is the last character in the PostOrder sequence.  We place it in the tree, and go to the next character in the PostOrder sequence.
For the InOrder sequence, we discard a node only if it
matches the current PostOrder character, or it is the parent of a
node.


Continuing with our example, we would compare R from the PostOrder sequence and X from the InOrder Sequence.  Since the inverted PostOrder sequence contains nodes in the form NRL and the inverted InOrder sequence contains nodes in the form RNL, we know  that R is a right child of M.   We next compare X and X, since they match we know not only that X is the right child of R, but that we have reached the end of the right children.  We now back up to X's parent, and continue the traversal by comparing P and Q. They obviously don't match, which means that P is the left child of R.  However, because of the traversal patterns, we also know that Q must be P's right child.  Why?  Because the inverted InOrder sequence just found a parent node. The next child must either be the root of the left subtree, or a right child of it.  If it is the root, the InOrder and PostOrder sequences will match.  If it is a right child, they won't.  You can verify this by examining
the following two sequences.

SEQUENCE 1: Tree traversals with node Q eliminated.

PostOrder: E L G P X R M

  InOrder: E G L M P R X

SEQUENCE 2: Tree traversals with node Q elimated, and Node N added
as a left child of P.

PostOrder: E L G N P X R M

  InOrder: E G L M N P R X