From ad183107055509e73c7a0740c1dd633f212d0f51 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 9 Jun 2019 11:54:36 -0500
Subject: woohoo, tree order traversal done!

Once again a lot of fun. I had about 3 months hiatus due to house
purchasing, where I didn't touch this exercise, more or less. Today I
made an effort following TDD and got the last post order traversal done!
I worried if edx/course staff stopped the auto grader. It turned out
they didn't. Really happy :)
---
 src/main/TreeTraversal.java     | 34 +++++++++++++++++++++++++---------
 src/test/TreeTraversalTest.java | 28 ++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+), 9 deletions(-)

diff --git a/src/main/TreeTraversal.java b/src/main/TreeTraversal.java
index d69164e..d7ca19d 100644
--- a/src/main/TreeTraversal.java
+++ b/src/main/TreeTraversal.java
@@ -23,7 +23,7 @@ public class TreeTraversal {
         }
     }
 
-    public static class TreeOrders {
+    static class TreeOrders {
         int n;
         int[] key, left, right;
 
@@ -42,7 +42,7 @@ public class TreeTraversal {
 
         List<Integer> inOrder() {
             Stack<Integer> keyIndexStack = new Stack<>();
-            ArrayList<Integer> result = new ArrayList<Integer>();
+            ArrayList<Integer> result = new ArrayList<>();
             // Finish the implementation
             // You may need to add a new recursive method to do that
             boolean walkLeft = true;
@@ -76,7 +76,7 @@ public class TreeTraversal {
         List<Integer> preOrder() {
             Stack<Integer> keyIndexStack = new Stack<>();
             Queue<Integer> keyIndexQueue = new LinkedList<>();
-            ArrayList<Integer> result = new ArrayList<Integer>();
+            ArrayList<Integer> result = new ArrayList<>();
             // Finish the implementation
             // You may need to add a new recursive method to do that
             boolean walkLeft = true;
@@ -113,13 +113,24 @@ public class TreeTraversal {
 
         List<Integer> postOrder() {
             Stack<Integer> keyIndexStack = new Stack<>();
-            ArrayList<Integer> result = new ArrayList<Integer>();
+            HashSet<Integer> peekedSet = new HashSet<>();
+            ArrayList<Integer> result = new ArrayList<>();
+//            ArrayList<Integer> bothSidesHaveBeenChecked = new ArrayList<>();
             // Finish the implementation
             // You may need to add a new recursive method to do that
             boolean walkLeft = true;
             int currentIndex = 0;
             keyIndexStack.push(currentIndex);
-            while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+//            while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+            while (!keyIndexStack.empty()) {
+                if (peekedSet.contains(currentIndex)) {
+                    result.add(key[currentIndex]);
+                    peekedSet.remove(currentIndex);
+                    keyIndexStack.pop();
+                    if (keyIndexStack.empty()) break;
+                    currentIndex = keyIndexStack.peek();
+                    continue;
+                }
                 if (walkLeft) {
                     if (left[currentIndex] != -1) {
                         currentIndex = left[currentIndex];
@@ -131,18 +142,23 @@ public class TreeTraversal {
                             keyIndexStack.pop();
                             currentIndex = keyIndexStack.peek();
                         } else {
+                            peekedSet.add(currentIndex);
                             currentIndex = right[currentIndex];
                             keyIndexStack.push(currentIndex);
                         }
                     }
                 } else {
                     if (right[currentIndex] != -1) {
+                        peekedSet.add(currentIndex);
                         currentIndex = right[currentIndex];
                         keyIndexStack.push(currentIndex);
                         walkLeft = true;
                     } else {
                         result.add(key[currentIndex]);
-                        keyIndexStack.pop();
+                        int i = keyIndexStack.pop();
+                        if (i != currentIndex)
+                            result.add(key[i]);
+                        if (keyIndexStack.empty()) break;
                         currentIndex = keyIndexStack.peek();
                     }
                 }
@@ -156,20 +172,20 @@ public class TreeTraversal {
             public void run() {
                 try {
                     new TreeTraversal().run();
-                } catch (IOException e) {
+                } catch (IOException ignored) {
                 }
             }
         }, "1", 1 << 26).start();
     }
 
-    public void print(List<Integer> x) {
+    private void print(List<Integer> x) {
         for (Integer a : x) {
             System.out.print(a + " ");
         }
         System.out.println();
     }
 
-    public void run() throws IOException {
+    private void run() throws IOException {
         TreeOrders tree = new TreeOrders();
         tree.read();
         print(tree.inOrder());
diff --git a/src/test/TreeTraversalTest.java b/src/test/TreeTraversalTest.java
index 1fd23ea..7e9773c 100644
--- a/src/test/TreeTraversalTest.java
+++ b/src/test/TreeTraversalTest.java
@@ -75,5 +75,33 @@ class TreeTraversalTest {
         assertEquals(20, tt.postOrder().get(8));
         assertEquals(0, tt.postOrder().get(9));
     }
+    @Test
+    void test2() {
+        TreeTraversal.TreeOrders tt = new TreeTraversal.TreeOrders();
+        tt.key = new int[]{782521203, 839950857, 248660666, 696374696, 971981286};
+        tt.left = new int[]{4, -1, 3, -1, 1};
+        tt.right = new int[]{-1, -1, -1, -1, 2};
+
+        assertEquals(5, tt.inOrder().size());
+        assertEquals(839950857, tt.inOrder().get(0));
+        assertEquals(971981286, tt.inOrder().get(1));
+        assertEquals(696374696, tt.inOrder().get(2));
+        assertEquals(248660666, tt.inOrder().get(3));
+        assertEquals(782521203, tt.inOrder().get(4));
+
+        assertEquals(5, tt.preOrder().size());
+        assertEquals(782521203, tt.preOrder().get(0));
+        assertEquals(971981286, tt.preOrder().get(1));
+        assertEquals(839950857, tt.preOrder().get(2));
+        assertEquals(248660666, tt.preOrder().get(3));
+        assertEquals(696374696, tt.preOrder().get(4));
+
+        assertEquals(5, tt.postOrder().size());
+        assertEquals(839950857, tt.postOrder().get(0));
+        assertEquals(696374696, tt.postOrder().get(1));
+        assertEquals(248660666, tt.postOrder().get(2));
+        assertEquals(971981286, tt.postOrder().get(3));
+        assertEquals(782521203, tt.postOrder().get(4));
+    }
 
 }
\ No newline at end of file
-- 
cgit v1.2.3