summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/main/TreeHeight.java156
-rw-r--r--src/test/TreeHeightTest.java47
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));
+ }
+}