TADM2E 5.7 - Revision history

HappyEngineer at 21:39, 17 June 2016

2016-06-17T21:39:03Z

Hezhe88: Remove the incorrect algo for part B

2016-06-09T02:03:43Z

Remove the incorrect algo for part B

Hezhe88: Undo revision 427 by Hezhe88 (talk)

2016-06-09T02:00:40Z

Undo revision 427 by Hezhe88 (talk)

Hezhe88: Undo revision 426 by Hezhe88 (talk)

2016-06-09T02:00:08Z

Undo revision 426 by Hezhe88 (talk)

Hezhe88: Undo revision 425 by Hezhe88 (talk)

2016-06-09T01:59:58Z

Undo revision 425 by Hezhe88 (talk)

Hezhe88: 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

2016-06-09T01:58:28Z

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

Hezhe88: Undo revision 412 by GreatSalmon (talk)

2016-06-09T01:56:16Z

Undo revision 412 by GreatSalmon (talk)

GreatSalmon at 16:22, 28 March 2016

2016-03-28T16:22:53Z

GreatSalmon at 22:17, 27 March 2016

2016-03-27T22:17:12Z

JoshuaSP at 06:52, 10 January 2015

2015-01-10T06:52:33Z

← Older revision		Revision as of 21:39, 17 June 2016
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:

← Older revision		Revision as of 02:03, 9 June 2016
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....~~
−
−	~~Use post-order to find left-most leaf > D~~
−	~~Use pre order to find parent > B~~
−	~~Use post order to find right child > E~~
−	~~Use pre-order to find parent of B > A~~
−	~~Use post order to find right subtree > G H F C~~
−	~~Use post order to find leftmost leaf > G~~
−	~~Use pre-order to find parent > F~~
−	~~Use post order to find right subtree > H~~
−	~~Use pre order to find parent of F > C~~
−	~~Use post order to find right subtree > null~~
−	~~Use pre order to find parent of C > A~~

	B. I have a counterexample. Consider both following trees:		B. I have a counterexample. Consider both following trees:

← Older revision		Revision as of 02:00, 9 June 2016
Line 63:		Line 63:
	Use post order to find right subtree > null		Use post order to find right subtree > null
	Use pre order to find parent of C > A		Use pre order to find parent of C > A
		+
		+	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.

← Older revision		Revision as of 02:00, 9 June 2016
Line 63:		Line 63:
	Use post order to find right subtree > null		Use post order to find right subtree > null
	Use pre order to find parent of C > A		Use pre order to find parent of C > A
−
−	~~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.~~

← Older revision		Revision as of 01:59, 9 June 2016
Line 63:		Line 63:
	Use post order to find right subtree > null		Use post order to find right subtree > null
	Use pre order to find parent of C > A		Use pre order to find parent of C > A
		+
		+	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.

← Older revision		Revision as of 01:58, 9 June 2016
Line 63:		Line 63:
	Use post order to find right subtree > null		Use post order to find right subtree > null
	Use pre order to find parent of C > A		Use pre order to find parent of C > A
−
−	~~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.~~

← Older revision		Revision as of 01:56, 9 June 2016
Line 67:		Line 67:

	1)		1)
−	A	+	A
−	B C	+	B C
−	D	+	D

	2)		2)

← Older revision		Revision as of 16:22, 28 March 2016
Line 67:		Line 67:

	1)		1)
−	A	+	A
−	B C	+	B C
−	D	+	D

	2)		2)

← Older revision		Revision as of 22:17, 27 March 2016
Line 63:		Line 63:
	Use post order to find right subtree > null		Use post order to find right subtree > null
	Use pre order to find parent of C > A		Use pre order to find parent of C > A
		+
		+	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.

@@ Line 21: / Line 21: @@
 It goes like this:
 .  Use pre-order traversal to find root.  (Beginning of tree/subtree)
 .  Use in-order traversal to find left sub tree  (All nodes before root)
 a. Process left sub tree if not leaf node
 . Use in-order traversal to find right sub tree  (All nodes after root)
 a. Process right sub tree if not leaf node
 So, our algorithm works like this:
-Use pre-order traversal to find root > A
+    Use pre-order traversal to find root > A
-Use in-order traversal to find left sub-tree > D B E
+    Use in-order traversal to find left sub-tree > D B E
-    Use pre-order traversal to find root > B
+        Use pre-order traversal to find root > B
-    Use in-order traversal to find left sub-tree > D
+        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 > E
-Use in-order traversal to find right sub-tree >  C G F H
+    Use in-order traversal to find right sub-tree >  C G F H
-    Use pre-order traversal to find root > C
+        Use pre-order traversal to find root > C
-    Use in-order traversal to find left sub-tree > null
+        Use in-order traversal to find left sub-tree > null
-    Use in-order traversal to find right sub-tree >  G F H
+        Use in-order traversal to find right sub-tree >  G F H
-        Use pre-order traversal to find root > F
+            Use pre-order traversal to find root > F
-        Use in-order traversal to find left sub-tree > G
+            Use in-order traversal to find left sub-tree > G
-        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.
 . Use post-order to find left most leaf. (first node)
 . Use pre order to find parent. (node preceding result 1)
 . Use post order to find right child. (Between left child and parent)
 a. Process right subtree if not leaf node
 . Return to step 2 to find parent of parent node.
 So....
-Use post-order to find left-most leaf > D
+    Use post-order to find left-most leaf > D
-Use pre order to find parent > B
+    Use pre order to find parent > B
-Use post order to find right child > E
+    Use post order to find right child > E
-Use pre-order to find parent of B > A
+    Use pre-order to find parent of B > A
-Use post order to find right subtree > G H F C
+    Use post order to find right subtree > G H F C
-       Use post order to find leftmost leaf > G
+           Use post order to find leftmost leaf > G
-       Use pre-order to find parent > F
+           Use pre-order to find parent > F
-       Use post order to find right subtree > H
+           Use post order to find right subtree > H
-       Use pre order to find parent of F > C
+           Use pre order to find parent of F > C
-       Use post order to find right subtree > null
+           Use post order to find right subtree > null
-       Use pre order to find parent of C > A
+           Use pre order to find parent of C > A