# Difference between revisions of "TADM2E 5.7"

From Algorithm Wiki

(Remove the incorrect algo for part B) |
|||

Line 47: | Line 47: | ||

1) | 1) | ||

− | + | A | |

− | + | / \ | |

− | D | + | B C |

+ | / | ||

+ | D | ||

2) | 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: | 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: |

## Latest revision as of 21:39, 17 June 2016

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.