Difference between revisions of "TADM2E 5.7"

From Algorithm Wiki
Jump to: navigation, search
(Undo revision 411 by GreatSalmon (talk) The counter example is not correct. Note the question here is "pre-order and in-order" not post-order)
 
(4 intermediate revisions by one other user not shown)
Line 42: Line 42:
 
             Use in-order traversal to find right sub-tree > H
 
             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....
+
B. I have a counterexample. Consider both following trees:
  
−
     Use post-order to find left-most leaf > D
+
1)
−
     Use pre order to find parent > B
+
    A
−
     Use post order to find right child > E
+
     / \
−
    Use pre-order to find parent of B > A
+
  B  C
−
    Use post order to find right subtree > G H F C
+
  /
−
          Use post order to find leftmost leaf > G
+
D
−
          Use pre-order to find parent > F
+
 
−
          Use post order to find right subtree > H
+
2)
−
          Use pre order to find parent of F > C
+
    A
−
          Use post order to find right subtree > null
+
     / \
−
          Use pre order to find parent of C > 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.

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.

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_5.7&oldid=431"