Binary search tree in Python

Binary Search Tree is a binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with values smaller than the node.
• The right subtree of a node contains only nodes with values greater than the node.
• The left and right subtree each must also be a binary search tree.

Based on the properties, we can implement a algorithm to check if a binary tree is binary search tree.

import sys


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


# left most node is minimum
def minVal(node):
    current = node

    while current.left != None:
        current = current.left

    return current.val


# right most node is maximum
def maxVal(node):
    current = node

    while current.right != None:
        current = current.right

    return current.val


# not efficient since some nodes are traversed multiple times
def isBst(node):
    if node == None:
        return True

    if node.left and node.val < minVal(node.left):
        return False
    if node.right and node.val > maxVal(node.right):
        return False

    if (not isBst(node.left)) or (not isBst(node.right)):
        return False

    return True


def isBstOptimal(node, min, max):
    if node == None:
        return True

    if node.val < min or node.val > max:
        return False

    return isBstOptimal(node.left, min, node.val) and isBstOptimal(
        node.right, node.val, max
    )


def binarySearch(node, target):
    if node == None:
        return False

    if node.val == target:
        return True

    if node.val > target:
        return binarySearch(node.left, target)
    elif node.val < target:
        return binarySearch(node.right, target)


#
#          6
#        /   \
#       4     8
#      / \   / \
#     2   5 7   9
#    / \
#   1   3
#
root = Node(6)
n1 = Node(4)
n2 = Node(8)
root.left = n1
root.right = n2
n3 = Node(2)
n4 = Node(5)
n1.left = n3
n1.right = n4
n5 = Node(7)
n6 = Node(9)
n2.left = n5
n2.right = n6
n7 = Node(1)
n8 = Node(3)
n3.left = n7
n3.right = n8

print(isBst(root))
print(isBstOptimal(root, -sys.maxsize, sys.maxsize))

n9 = Node(9)
n7.left = n9

print(isBst(root))
print(isBstOptimal(root, -sys.maxsize, sys.maxsize))

print(binarySearch(root, 8))
print(binarySearch(root, 11))
print(binarySearch(root, -1))