TADM2E 5.7

Let's use the following tree for demonstration purposes:

                        A
                
                  B          C

             D       E             F

                                  G     H

Pre-order traversal: A B D E C F G H In-order traversal: D B E A C G F H Post-order traversal: D E B G H F C A

Part A.

We create a recursive algorithm that processes sub trees until we arrive at single leaf nodes.

It goes like this:

   1.  Use pre-order traversal to find root.  (Beginning of tree/subtree)
   2.  Use in-order traversal to find left sub tree  (All nodes before root)
          2a. Process left sub tree if not leaf node
   3. Use in-order traversal to find right sub tree  (All nodes after root)
          3a. Process right sub tree if not leaf node

So, our algorithm works like this:

   Use pre-order traversal to find root > A
   Use in-order traversal to find left sub-tree > D B E
       Use pre-order traversal to find root > B
       Use in-order traversal to find left sub-tree > D
       Use in-order traversal to find right sub-tree > E
   Use in-order traversal to find right sub-tree >  C G F H
       Use pre-order traversal to find root > C
       Use in-order traversal to find left sub-tree > null
       Use in-order traversal to find right sub-tree >  G F H
           Use pre-order traversal to find root > F
           Use in-order traversal to find left sub-tree > G
           Use in-order traversal to find right sub-tree > H

B. I have a counterexample. Consider both following trees:

1)

   A
 B   C

D

2)

  A
B  C
 D

In tree 1, D is the left child of B. In tree 2, D is the right child of B. For both trees, the traversals are: Pre-order: A B D C Post-order: D B C A

So there is no way of rebuilding a unique tree from these two traversals.