Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- class Node:
- data = -1
- left = None
- right = None
- def is_bst_impl(node, n_min, n_max):
- if node.data < n_min or node.data > n_max:
- return False
- l_is_bst = True
- if node.left is not None:
- if node.left.data < node.data:
- l_is_bst = is_bst_impl(node.left, n_min, node.data)
- else:
- l_is_bst = False
- r_is_bst = True
- if node.right is not None:
- if node.right.data > node.data:
- r_is_bst = is_bst_impl(node.right, node.data, n_max)
- else:
- r_is_bst = False
- return l_is_bst and r_is_bst
- def is_bst(root):
- if root is None:
- return True
- return is_bst_impl(root, -sys.maxsize - 1, sys.maxsize)
- def task():
- n = int(input())
- if n <= 0:
- print("CORRECT")
- return
- root = Node()
- lines = []
- for i in range(n):
- line = list(map(int, input().split()))
- lines.append(line)
- fill_tree(root, lines, 0)
- flag = is_bst(root)
- if flag is True:
- print("CORRECT")
- else:
- print("INCORRECT")
- def fill_tree(node, lines_, pos_):
- line_ = lines_[pos_]
- node.data = line_[0]
- if line_[1] != -1:
- node.left = Node()
- fill_tree(node.left, lines_, line_[1])
- if line_[2] != -1:
- node.right = Node()
- fill_tree(node.right, lines_, line_[2])
- if __name__ == "__main__":
- task()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement