# TADM2E 5.7

From Algorithm Wiki

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.