From ced86db4658bdc3aba7e3f59991c1723ceae0531 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 12 Jun 2019 10:55:58 -0500
Subject: 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 :)
---
 sources/tree_bst_check.py   | 58 +++++++++++++++++++++++++++++++++++++++++++++
 tests/tree_bst_checkTest.py | 15 ++++++++++++
 2 files changed, 73 insertions(+)
 create mode 100644 sources/tree_bst_check.py
 create mode 100644 tests/tree_bst_checkTest.py

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