From cefc6a2cd763e09adb8b4df33697df4a2cb5ddab Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 10 Jan 2019 20:36:29 -0600
Subject: Tree height done!

Fun exercise. Interesting to experience the mentality change
of creating classes in Python, after first creating it in Java.
I removed the parent property in Python class since it's not
used. Object aliasing caused a bug that took me a bit to figure out.
---
 sources/tree_height.py | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)
 create mode 100644 sources/tree_height.py

(limited to 'sources')

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))
-- 
cgit v1.2.3