Tukukkk

Given a binary tree with integers as its keys I need to test whether it is a correct binary search tree. Duplicate integers allowed. Smaller elements are to the left, bigger elements are to the right, and duplicates are always to the right

def IsBinarySearchTree(tree):

  # Implement correct algorithm here

  min = -sys.maxsize

  max = sys.maxsize

  key_hash = {}



  def is_bst_until(idx_node,maxi,mini, is_left = False):

    if idx_node == -1:

      return True



    node = tree[idx_node]

    key = node[0]

    idx_left = node[1]

    idx_right = node[2]    



    if (key>maxi) or (key<mini):

      return False



    if is_left:

      if (key==mini):

        return False



    return (is_bst_until(idx_right, maxi, key)) and (is_bst_until(idx_left, key-1, mini, is_left=True))



  if len(tree) == 0:

      return True

  return is_bst_until(0, max, min)





def main():

  nodes = int(sys.stdin.readline().strip())

  tree = 

  for i in range(nodes):

    tree.append(list(map(int, sys.stdin.readline().strip().split())))

  if IsBinarySearchTree(tree):

    print("CORRECT")

  else:

    print("INCORRECT")



threading.Thread(target=main).start()

Input Format. The first line contains the number of vertices n. The vertices of the tree are numbered from 0 to n−1. Vertex 0 is the root. The next n lines contain information about vertices 0, 1, ..., 𝑛 − 1 in order. Each of these lines contains three integers key, left and right

Output Format. If the given binary tree is a correct binary search tree, output one word “CORRECT”. Otherwise, output one word “INCORRECT”.

Examples:

3

2 1 2

2 -1 -1

3 -1 -1

#Incorrect



5

1 -1 1

2 -1 2

3 -1 3

4 -1 4

5 -1 -1

#Correct

Frankly speaking I don't think my solution is a good one. I'm concerned about is_left

I'll appreciate if you suggest me an alternative solution