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. For pre & post order, the algorithm works like this.

   1. Use post-order to find left most leaf. (first node)
   2. Use pre order to find parent. (node preceding result 1)
   3. Use post order to find right child. (Between left child and parent)
             3a. Process right subtree if not leaf node
   4. Return to step 2 to find parent of parent node.

So....

   Use post-order to find left-most leaf > D
   Use pre order to find parent > B
   Use post order to find right child > E
   Use pre-order to find parent of B > A
   Use post order to find right subtree > G H F C
          Use post order to find leftmost leaf > G
          Use pre-order to find parent > F
          Use post order to find right subtree > H
          Use pre order to find parent of F > C
          Use post order to find right subtree > null
          Use pre order to find parent of C > A

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.