1 files changed, 71 insertions, 0 deletions
diff --git a/sources/tree_height.py b/sources/tree_height.py
new file mode 100644
index 0000000..9cebe3a
--- /dev/null
+++ b/sources/tree_height.py
@@ -0,0 +1,71 @@
+# Uses python3
+import queue
+
+
+class Node(object):
+    def __init__(self, key):
+        self._key = key
+        self.children = []
+
+    @property
+    def key(self):
+        return self._key
+
+    @key.setter
+    def key(self, key):
+        self._key = key
+
+    def add_child(self, child):
+        self.children.extend([child])
+
+    def get_children(self):
+        return self.children
+
+
+def tree_level_counter(nodes, root_index):
+    level_counter = 1
+    q = queue.Queue()
+    pop_count = 0
+    child_count = len(nodes[root_index].get_children())
+    grand_children_count = 0
+    for i in range(child_count):
+        q.put(nodes[root_index].get_children()[i])
+    while not q.empty():
+        if pop_count < child_count:
+            node = q.get()
+            i = len(node.get_children())
+            if i != 0:
+                for j in range(i):
+                    q.put(node.get_children()[j])
+            grand_children_count = grand_children_count + i
+            pop_count = pop_count + 1
+        else:
+            pop_count = 0
+            child_count = grand_children_count
+            grand_children_count = 0
+            level_counter = level_counter + 1
+    return level_counter + 1
+
+
+def get_height(a):
+    # The code below has the bug of alias/referencing. Code after that fixed it.
+    # nodes = [Node(-5)] * len(a)
+    nodes = []
+    for i in range(len(a)):
+        nodes.append(Node(i))
+    root_index = 0
+
+    for i in range(len(a)):
+        parent_index = a[i]
+        nodes[i].key = i
+        if parent_index == -1:
+            root_index = i
+        else:
+            nodes[parent_index].add_child(nodes[i])
+    return tree_level_counter(nodes, root_index)
+
+
+if __name__ == '__main__':
+    n = int(input())
+    parents = list(map(int, input().split()))
+    print(get_height(parents))