Validate BST

Implement a function to check if a binary tree is a binary search tree.

Solution

A binary search tree is a binary tree that satisfies the following relationship: each left child is less than the parent, and each right child is greater than or equal to the parent. We can use a recursive call to traverse the tree, starting with the root node.

def validate_bst(node):
  flag = True

  if(node.left):
    if not (node.left.key < node.key):
      flag = False
    if not validate_bst(node.left):
      flag = False

  if(node.right):
    if not (node.right.key >= node.key):
      flag = False
    if not validate_bst(node.right):
      flag = False

  return flag