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));
+    }
+}