Difference between revisions of "TADM2E 5.7"

From Algorithm Wiki
Jump to: navigation, search
(Remove the incorrect algo for part B)
 
Line 47: Line 47:
  
 
1)
 
1)
    A
+
    A
  B  C
+
    / \
D
+
  B  C
 +
  /
 +
D
  
 
2)
 
2)
  A
+
    A
B C
+
    / \
  D
+
  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.