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.