Advertisement
Purposelessness

Untitled

Feb 2nd, 2023
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. import sys
  2.  
  3.  
  4. class Node:
  5. data = -1
  6. left = None
  7. right = None
  8.  
  9.  
  10. def is_bst_impl(node, n_min, n_max):
  11. if node.data < n_min or node.data > n_max:
  12. return False
  13.  
  14. l_is_bst = True
  15. if node.left is not None:
  16. if node.left.data < node.data:
  17. l_is_bst = is_bst_impl(node.left, n_min, node.data)
  18. else:
  19. l_is_bst = False
  20.  
  21. r_is_bst = True
  22. if node.right is not None:
  23. if node.right.data > node.data:
  24. r_is_bst = is_bst_impl(node.right, node.data, n_max)
  25. else:
  26. r_is_bst = False
  27. return l_is_bst and r_is_bst
  28.  
  29.  
  30. def is_bst(root):
  31. if root is None:
  32. return True
  33. return is_bst_impl(root, -sys.maxsize - 1, sys.maxsize)
  34.  
  35.  
  36. def task():
  37. n = int(input())
  38. if n <= 0:
  39. print("CORRECT")
  40. return
  41. root = Node()
  42. lines = []
  43. for i in range(n):
  44. line = list(map(int, input().split()))
  45. lines.append(line)
  46. fill_tree(root, lines, 0)
  47. flag = is_bst(root)
  48. if flag is True:
  49. print("CORRECT")
  50. else:
  51. print("INCORRECT")
  52.  
  53.  
  54. def fill_tree(node, lines_, pos_):
  55. line_ = lines_[pos_]
  56. node.data = line_[0]
  57. if line_[1] != -1:
  58. node.left = Node()
  59. fill_tree(node.left, lines_, line_[1])
  60. if line_[2] != -1:
  61. node.right = Node()
  62. fill_tree(node.right, lines_, line_[2])
  63.  
  64.  
  65. if __name__ == "__main__":
  66. task()
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement