summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2019-01-10 20:36:29 -0600
committerHaidong Ji2019-01-10 20:36:29 -0600
commitcefc6a2cd763e09adb8b4df33697df4a2cb5ddab (patch)
tree2350644ce1626e8c0271a0a4fa6db78ec904c5fc
parent374f0d359768aa2891b2a6dc24f195f0ec277ab2 (diff)
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.
-rw-r--r--sources/tree_height.py71
-rw-r--r--tests/tree_height.py36
2 files changed, 107 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))
diff --git a/tests/tree_height.py b/tests/tree_height.py
new file mode 100644
index 0000000..75a1382
--- /dev/null
+++ b/tests/tree_height.py
@@ -0,0 +1,36 @@
+import unittest
+
+from sources.tree_height import get_height
+
+class MyTestCase(unittest.TestCase):
+ def test1(self):
+ a = [4, -1, 4, 1, 1]
+ self.assertEqual(3, get_height(a))
+
+ def test2(self):
+ a = [-1, 0, 4, 0, 3]
+ self.assertEqual(4, get_height(a))
+
+ # def test3(self):
+ # a = [4, -1, 4, 1, 1]
+ # self.assertEqual(3, getHeightNaive(a))
+ #
+ # def test4(self):
+ # a = [-1, 0, 4, 0, 3]
+ # self.assertEqual(4, getHeightNaive(a))
+ #
+ # def test5(self):
+ # a = [9, 7, 5, 5, 2, 9, 9, 9, 2, -1]
+ # self.assertEqual(4, getHeightNaive(a))
+
+ def test6(self):
+ a = [9, 7, 5, 5, 2, 9, 9, 9, 2, -1]
+ self.assertEqual(4, get_height(a))
+
+ def test7(self):
+ a = [8, 8, 5, 6, 7, 3, 1, 6, -1, 5]
+ self.assertEqual(6, get_height(a))
+
+
+if __name__ == '__main__':
+ unittest.main()