1 files changed, 58 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")