summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
Diffstat (limited to 'sources')
-rw-r--r--sources/tree_height.py71
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))