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 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) create mode 100644 sources/tree_bst_check.py (limited to 'sources') 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") -- cgit v1.2.3