Given the head node of a binary tree, check if the tree is a binary search tree.

check_bst.py

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


def is_bst_rec(node: Node, min_v: object = None, max_v: object = None) -> bool: # todo should use float('inf') and float('-inf')
    if (min_v and node.val < min_v) or (max_v and node.val > max_v):
        return False
    if node.left:
        if node.left.val > node.val or not is_bst_rec(node.left, min_v, node.val):
            return False
    if node.right:
        if node.right.val < node.val or not is_bst_rec(node.right, node.val, max_v):
            return False
    return True


def is_bst_iter(node: Node):
    if node is None:
        return True

    stack = []
    last = float('-inf')

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack.pop()
            if node.val <= last:
                return False
            last = node.val
            node = node.right
    return True


if __name__ == '__main__':
    a = Node(1)
    b = Node(2)
    c = Node(3)
    d = Node(4)

    c.left = b
    b.left = a

    print(is_bst_iter(c))

    c.right = d
    print(is_bst_iter(c))

    c.right = None
    b.right = d
    print(is_bst_iter(c))