Tree height recursive version done!

Following example starter code, I had to specify stackSize when creating the thread. Without it, it won't pass tests due to stack overflow error. I'll still try to work out an iterative version using Queue. We'll see.

2 files changed, 203 insertions, 0 deletions

diff --git a/src/main/TreeHeight.java b/src/main/TreeHeight.java
new file mode 100644
index 0000000..0e5119a
--- /dev/null
+++ b/src/main/TreeHeight.java
@@ -0,0 +1,156 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.*;
+
+class TreeHeight {
+    static class FastScanner {
+        StringTokenizer tok = new StringTokenizer("");
+        BufferedReader in;
+
+        FastScanner(InputStream in) {
+            this.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());
+        }
+    }
+
+    static class Node<T> {
+        private T key;
+        private Node<T> parent = null;
+        private List<Node<T>> children = new ArrayList<>();
+
+        Node(T key) {
+            this.key = key;
+        }
+
+        void addChild(Node<T> child) {
+            child.setParent(this);
+            this.children.add(child);
+        }
+
+        private void setParent(Node<T> parent) {
+            this.parent = parent;
+        }
+
+        public Node<T> getParent(Node<T> parent) {
+            return this.parent;
+        }
+
+        List<Node<T>> getChildren() {
+            return children;
+        }
+
+        public T getKey() {
+            return key;
+        }
+
+        void setKey(T key) {
+            this.key = key;
+        }
+
+    }
+
+    static int getHeight(int[] a) {
+        Node[] nodes = new Node[a.length];
+        int rootIndex = 0;
+        for (int i = 0; i < a.length; i++) {
+            nodes[i] = new Node<>(-5);
+        }
+        for (int i = 0; i < a.length; i++) {
+            int parentIndex = a[i];
+            if (parentIndex == -1) {
+                rootIndex = i;
+                nodes[i].setKey(i);
+            } else {
+                nodes[i].setKey(i);
+                nodes[parentIndex].addChild(nodes[i]);
+            }
+        }
+//        return treeLevelCounter(nodes, rootIndex);
+        return treeLevelCounterRecursive(nodes[rootIndex]);
+    }
+
+    private static int treeLevelCounterRecursive(Node<Integer> node) {
+        if (node.getChildren().size() == 0)
+            return 1;
+        int maxCount = Integer.MIN_VALUE;
+        int tempCount;
+        for (int i = 0; i < node.getChildren().size(); i++) {
+            tempCount = treeLevelCounterRecursive(node.getChildren().get(i));
+            if (tempCount > maxCount)
+                maxCount = tempCount;
+        }
+        return 1 + maxCount;
+    }
+
+    private static int treeLevelCounter(Node<Integer>[] nodes, int rootIndex) {
+        int levelCounter = 0;
+        Queue<Node<Integer>> q = new LinkedList<>();
+        q.add(nodes[rootIndex]);
+        while (!q.isEmpty()) {
+            Node<Integer> n = q.remove();
+            int i = n.getChildren().size();
+            if (i != 0) {
+                for (int j = 0; j < i; j++) {
+                    q.add(n.getChildren().get(j));
+                }
+            }
+            levelCounter = levelCounter + 1;
+        }
+        return levelCounter;
+    }
+
+    static int getHeightNaive(int[] a) {
+        int n = a.length;
+        int maxHeight = 0;
+        for (int vertex = 0; vertex < n; vertex++) {
+            int height = 0;
+            for (int i = vertex; i != -1; i = a[i])
+                height++;
+            maxHeight = Math.max(maxHeight, height);
+        }
+        return maxHeight;
+    }
+
+//    public static void main(String[] args) throws IOException {
+//        FastScanner scanner = new FastScanner(System.in);
+//        int n = scanner.nextInt();
+//        int[] a = new int[n];
+//        for (int i = 0; i < n; i++) {
+//            a[i] = scanner.nextInt();
+//        }
+//        System.out.println(getHeight(a));
+//    }
+    public static void main(String[] args) {
+        new Thread(null, new Runnable() {
+            public void run() {
+                try {
+                    runTheThing();
+                } catch (IOException ignored) {
+                }
+            }
+        }, "1", 1 << 26).start();
+
+    }
+
+    private static void runTheThing() throws IOException {
+        FastScanner scanner = new FastScanner(System.in);
+        int n = scanner.nextInt();
+        int[] a = new int[n];
+        for (int i = 0; i < n; i++) {
+            a[i] = scanner.nextInt();
+        }
+        System.out.println(getHeight(a));
+    }
+
+}
diff --git a/src/test/TreeHeightTest.java b/src/test/TreeHeightTest.java
new file mode 100644
index 0000000..0fe3e57
--- /dev/null
+++ b/src/test/TreeHeightTest.java
@@ -0,0 +1,47 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class TreeHeightTest {
+    @Test
+    void test1() {
+        int[] a = {4, -1, 4, 1, 1};
+        assertEquals(3, TreeHeight.getHeight(a));
+    }
+
+    @Test
+    void test2() {
+        int[] a = {-1, 0, 4, 0, 3};
+        assertEquals(4, TreeHeight.getHeight(a));
+    }
+
+    @Test
+    void test3() {
+        int[] a = {4, -1, 4, 1, 1};
+        assertEquals(3, TreeHeight.getHeightNaive(a));
+    }
+
+    @Test
+    void test4() {
+        int[] a = {-1, 0, 4, 0, 3};
+        assertEquals(4, TreeHeight.getHeightNaive(a));
+    }
+
+    @Test
+    void test5() {
+        int[] a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1};
+        assertEquals(4, TreeHeight.getHeightNaive(a));
+    }
+
+    @Test
+    void test6() {
+        int[] a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1};
+        assertEquals(4, TreeHeight.getHeight(a));
+    }
+
+    @Test
+    void test7() {
+        int[] a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5};
+        assertEquals(6, TreeHeight.getHeight(a));
+    }
+}