Binary Search Tree
Traverse the tree in natural order and test if each node is between the previous and the next node. Properly detect duplicate values. If a wrong sub-tree is encountered immediately stop the script and indicate the error.
See code below
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
# python3 import sys, threading sys.setrecursionlimit(10**6) # max depth of recursion threading.stack_size(2**27) # new thread will get stack of such size class TreeOrders: def __init__(self): """We can't assume a proper BST description, only a proper binary tree. In order to use the BST class we have to generate and assign keys while creating the tree. The 'values' will be assigned as a new 'label' field. The first node is going to be the initial root. """ n = int(input()) self.nodes = [list(map(int, sys.stdin.readline().split())) for i in range(n)] def value(self, i): """Return the value (key) of the node at index i.""" return self.nodes[i][0] def left(self, i): """Return the index of the left child of node at index i or None if the node doesn't have a left child.""" result = self.nodes[i][1] if result == -1: return None else: return result def right(self, i): """Return the index of the right child of node at index i or None if the node doesn't have a right child.""" result = self.nodes[i][2] if result == -1: return None else: return result def is_bst(self, index=0): """Traverse the tree in "natural" order and test if each node is between the previous and the next node. Properly detect duplicate values. If a wrong subtree is encountered immediately report and stop the script.""" # find children l = self.left(index) r = self.right(index) # get left and right subtrees (if present) left = self.is_bst(index=l) if l else [] right = self.is_bst(index=r) if r else [] if left and self.value(left[-1]) >= self.value(index) or right and self.value(right[0]) < self.value(index): fail() return left[0::-1] + [index] + right[0::-1] def fail(): print("INCORRECT") sys.exit() def main(): tree = TreeOrders() if len(tree.nodes) == 0 or tree.is_bst(): print("CORRECT") threading.Thread(target=main).start() |
Leave a Reply