summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2019-06-12 10:55:58 -0500
committerHaidong Ji2019-06-12 10:55:58 -0500
commitced86db4658bdc3aba7e3f59991c1723ceae0531 (patch)
tree9a1d9721364095eedfaebe2d2a235f69b5a366dd
parent560bb4c29cbbfd940e2773df0ff28d0315b16517 (diff)
Binary Search Tree check done!
Easy after Java version is done. I'm happy that I did this in 3 languages (Java, Python, C++). I can really tell that Python is more succinct, whereas Java is really verbose. Fun stuff :)
-rw-r--r--sources/tree_bst_check.py58
-rw-r--r--tests/tree_bst_checkTest.py15
2 files changed, 73 insertions, 0 deletions
diff --git a/sources/tree_bst_check.py b/sources/tree_bst_check.py
new file mode 100644
index 0000000..28af017
--- /dev/null
+++ b/sources/tree_bst_check.py
@@ -0,0 +1,58 @@
+# python3
+import sys
+
+
+def isBst(key, left, right):
+ if len(key) == 0:
+ return True
+ keyIndexStack = []
+ result = []
+ walkLeft = True
+
+ currentIndex = 0
+ keyIndexStack.append(currentIndex)
+ while len(keyIndexStack) != 0 or right[currentIndex] != -1:
+ if walkLeft:
+ if left[currentIndex] != -1:
+ if key[left[currentIndex]] >= key[currentIndex]:
+ return False
+ currentIndex = left[currentIndex]
+ keyIndexStack.append(currentIndex)
+ else:
+ i = keyIndexStack.pop()
+ if len(result) > 0:
+ if key[i] <= result[-1]:
+ return False
+ result.append(key[i])
+ walkLeft = False
+ else:
+ if right[currentIndex] != -1:
+ if key[right[currentIndex]] <= key[currentIndex]:
+ return False
+ currentIndex = right[currentIndex]
+ keyIndexStack.append(currentIndex)
+ walkLeft = True
+ else:
+ if len(keyIndexStack) != 0:
+ currentIndex = keyIndexStack.pop()
+ if len(result) > 0:
+ if key[currentIndex] <= result[-1]:
+ return False
+ result.append(key[currentIndex])
+ return True
+
+
+if __name__ == '__main__':
+ n = int(sys.stdin.readline())
+ key = [0 for i in range(n)]
+ left = [0 for i in range(n)]
+ right = [0 for i in range(n)]
+ for i in range(n):
+ [a, b, c] = map(int, sys.stdin.readline().split())
+ key[i] = a
+ left[i] = b
+ right[i] = c
+ if isBst(key, left, right):
+ print("CORRECT")
+ else:
+ print("INCORRECT")
diff --git a/tests/tree_bst_checkTest.py b/tests/tree_bst_checkTest.py
new file mode 100644
index 0000000..6924168
--- /dev/null
+++ b/tests/tree_bst_checkTest.py
@@ -0,0 +1,15 @@
+import unittest
+
+from sources.tree_bst_check import isBst
+
+class MyTestCase(unittest.TestCase):
+ def test_something(self):
+ key = [2, 1, 3]
+ left = [1, -1, -1]
+ right = [2, -1, -1]
+
+ self.assertTrue(isBst(key, left, right))
+
+
+if __name__ == '__main__':
+ unittest.main()