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

3 files changed, 237 insertions, 0 deletions

diff --git a/.idea/encodings.xml b/.idea/encodings.xml
new file mode 100644
index 0000000..15a15b2
--- /dev/null
+++ b/.idea/encodings.xml
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="Encoding" addBOMForNewFiles="with NO BOM" />
+</project>
\ No newline at end of file
diff --git a/src/main/TreeTraversal.java b/src/main/TreeTraversal.java
new file mode 100644
index 0000000..fee494c
--- /dev/null
+++ b/src/main/TreeTraversal.java
@@ -0,0 +1,173 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.*;
+
+public class TreeTraversal {
+    static class FastScanner {
+        StringTokenizer tok = new StringTokenizer("");
+        BufferedReader in;
+
+        FastScanner() {
+            in = new BufferedReader(new InputStreamReader(System.in));
+        }
+
+        String next() throws IOException {
+            while (!tok.hasMoreElements())
+                tok = new StringTokenizer(in.readLine());
+            return tok.nextToken();
+        }
+
+        int nextInt() throws IOException {
+            return Integer.parseInt(next());
+        }
+    }
+
+    public static class TreeOrders {
+        int n;
+        int[] key, left, right;
+
+        void read() throws IOException {
+            FastScanner in = new FastScanner();
+            n = in.nextInt();
+            key = new int[n];
+            left = new int[n];
+            right = new int[n];
+            for (int i = 0; i < n; i++) {
+                key[i] = in.nextInt();
+                left[i] = in.nextInt();
+                right[i] = in.nextInt();
+            }
+        }
+
+        List<Integer> inOrder() {
+            Stack<Integer> keyIndexStack = new Stack<>();
+            ArrayList<Integer> result = new ArrayList<Integer>();
+            // 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) {
+                if (walkLeft) {
+                    if (left[currentIndex] != -1) {
+                        currentIndex = left[currentIndex];
+                        keyIndexStack.push(currentIndex);
+                    } else {
+                        result.add(key[keyIndexStack.pop()]);
+                        walkLeft = false;
+                    }
+                } else {
+                    if (right[currentIndex] != -1) {
+                        currentIndex = right[currentIndex];
+                        keyIndexStack.push(currentIndex);
+                        walkLeft = true;
+                    } else {
+                        if (!keyIndexStack.empty()) {
+                            currentIndex = keyIndexStack.pop();
+                            result.add(key[currentIndex]);
+                        }
+                    }
+                }
+            }
+            return result;
+        }
+
+        List<Integer> preOrder() {
+            Stack<Integer> keyIndexStack = new Stack<>();
+            Queue<Integer> keyIndexQueue = new LinkedList<>();
+            ArrayList<Integer> result = new ArrayList<Integer>();
+            // Finish the implementation
+            // You may need to add a new recursive method to do that
+            boolean walkLeft = true;
+            int currentIndex = 0;
+            keyIndexStack.push(currentIndex);
+            keyIndexQueue.add(currentIndex);
+            while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+                if (walkLeft) {
+                    if (left[currentIndex] != -1) {
+                        currentIndex = left[currentIndex];
+                        keyIndexQueue.add(currentIndex);
+                        keyIndexStack.push(currentIndex);
+                    } else {
+                        keyIndexStack.pop();
+                        walkLeft = false;
+                        result.add(key[keyIndexQueue.remove()]);
+                    }
+                } else {
+                    if (right[currentIndex] != -1) {
+                        currentIndex = right[currentIndex];
+                        keyIndexQueue.add(currentIndex);
+                        keyIndexStack.push(currentIndex);
+                        walkLeft = true;
+                    } else {
+                        if (!keyIndexStack.empty()) {
+                            currentIndex = keyIndexStack.pop();
+                            result.add(key[keyIndexQueue.remove()]);
+                        }
+                    }
+                }
+            }
+            return result;
+        }
+
+        List<Integer> postOrder() {
+            Stack<Integer> keyIndexStack = new Stack<>();
+            ArrayList<Integer> result = new ArrayList<Integer>();
+            // 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) {
+                if (walkLeft) {
+                    if (left[currentIndex] != -1) {
+                        currentIndex = left[currentIndex];
+                        keyIndexStack.push(currentIndex);
+                    } else {
+                        result.add(key[keyIndexStack.pop()]);
+                        walkLeft = false;
+                    }
+                } else {
+                    if (right[currentIndex] != -1) {
+                        currentIndex = right[currentIndex];
+                        keyIndexStack.push(currentIndex);
+                        walkLeft = true;
+                    } else {
+                        if (!keyIndexStack.empty()) {
+                            currentIndex = keyIndexStack.pop();
+                            result.add(key[currentIndex]);
+                        }
+                    }
+                }
+            }
+            return result;
+        }
+    }
+
+    static public void main(String[] args) throws IOException {
+        new Thread(null, new Runnable() {
+            public void run() {
+                try {
+                    new TreeTraversal().run();
+                } catch (IOException e) {
+                }
+            }
+        }, "1", 1 << 26).start();
+    }
+
+    public void print(List<Integer> x) {
+        for (Integer a : x) {
+            System.out.print(a + " ");
+        }
+        System.out.println();
+    }
+
+    public void run() throws IOException {
+        TreeOrders tree = new TreeOrders();
+        tree.read();
+        print(tree.inOrder());
+        print(tree.preOrder());
+        print(tree.postOrder());
+    }
+}
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