From acff8424e09a3531cae111a93fb0f6fce1d4404e Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 22 Mar 2019 18:02:48 -0500
Subject: In-order and pre-order binary tree traversal done

I worked this out myself, using iterative approach instead of recursive
to avoid stack overflow issues. Post-order traversal not done yet. I'll
likely follow pseudo code from this wiki page to get that done:
https://en.wikipedia.org/wiki/Tree_traversal
---
 src/test/TreeTraversalTest.java | 60 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)
 create mode 100644 src/test/TreeTraversalTest.java

(limited to 'src/test')

diff --git a/src/test/TreeTraversalTest.java b/src/test/TreeTraversalTest.java
new file mode 100644
index 0000000..336b86c
--- /dev/null
+++ b/src/test/TreeTraversalTest.java
@@ -0,0 +1,60 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class TreeTraversalTest {
+    @Test
+    void test() {
+        TreeTraversal.TreeOrders tt = new TreeTraversal.TreeOrders();
+        tt.key = new int[]{4, 2, 5, 1, 3};
+        tt.left = new int[]{1, 3, -1, -1, -1};
+        tt.right = new int[]{2, 4, -1, -1, -1};
+
+        assertEquals(5, tt.inOrder().size());
+        assertEquals(1, tt.inOrder().get(0));
+        assertEquals(2, tt.inOrder().get(1));
+        assertEquals(3, tt.inOrder().get(2));
+        assertEquals(4, tt.inOrder().get(3));
+        assertEquals(5, tt.inOrder().get(4));
+
+        assertEquals(5, tt.preOrder().size());
+        assertEquals(4, tt.preOrder().get(0));
+        assertEquals(2, tt.preOrder().get(1));
+        assertEquals(1, tt.preOrder().get(2));
+        assertEquals(3, tt.preOrder().get(3));
+        assertEquals(5, tt.preOrder().get(4));
+    }
+
+    @Test
+    void test1() {
+        TreeTraversal.TreeOrders tt = new TreeTraversal.TreeOrders();
+        tt.key = new int[]{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
+        tt.left = new int[]{7, -1, -1, 8, 3, -1, 1, 5, -1, -1};
+        tt.right = new int[]{2, -1, 6, 9, -1, -1, -1, 4, -1, -1};
+
+        assertEquals(10, tt.inOrder().size());
+        assertEquals(50, tt.inOrder().get(0));
+        assertEquals(70, tt.inOrder().get(1));
+        assertEquals(80, tt.inOrder().get(2));
+        assertEquals(30, tt.inOrder().get(3));
+        assertEquals(90, tt.inOrder().get(4));
+        assertEquals(40, tt.inOrder().get(5));
+        assertEquals(0, tt.inOrder().get(6));
+        assertEquals(20, tt.inOrder().get(7));
+        assertEquals(10, tt.inOrder().get(8));
+        assertEquals(60, tt.inOrder().get(9));
+
+        assertEquals(10, tt.preOrder().size());
+        assertEquals(0, tt.preOrder().get(0));
+        assertEquals(70, tt.preOrder().get(1));
+        assertEquals(50, tt.preOrder().get(2));
+        assertEquals(40, tt.preOrder().get(3));
+        assertEquals(30, tt.preOrder().get(4));
+        assertEquals(80, tt.preOrder().get(5));
+        assertEquals(90, tt.preOrder().get(6));
+        assertEquals(20, tt.preOrder().get(7));
+        assertEquals(60, tt.preOrder().get(8));
+        assertEquals(10, tt.preOrder().get(9));
+    }
+
+}
\ No newline at end of file
-- 
cgit v1.2.3