How to check if the given Node is the root of a BST in Python?

Question

As we knew, in a BST, the left nodes of the root must be smaller and the right nodes must be bigger than the root. We also knew that the node has data, left, and right attributes. I need to define a function to check if the given root is the root of a BST or not. If it's a BST, the function must return True and if not, False.

This is my code:

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.left = None
        self.right = None

    def is_bst(root: Node):
        if root is None or (root.left is None and root.right is None):
            return True
        elif root.right is None:
            return root.left.data < root.data and is_bst(root.left)
        elif root.left is None:
            return root.right.data > root.data and is_bst(root.right)

    return is_bst(root.left) and is_bst(root.right)

a = Node(2)
a.left = Node(4)
a.right = Node(1)
print(is_bst(a))

You can see I did make a tree that is not BST but it returns True anyway...

Answer 1

change the is_bst to:

def is_bst(root):
    # stop condition
    if root is None:
        return True

    # check left < root
    if root.left is not None:
        if root.data <= root.left.data:
            return False

    #check right > root
    if root.right is not None:
        if root.data >= root.right.data:
            return False

    # continue checking recursivly.
    return is_bst(root.left) and is_bst(root.right)

personally, I rather not deal with it and just use some open-source framework (like networkx)... it has a bunch of helper functions that you can query your data structures...

Answer 2

You forgot to check root.left.data < root.data < root.right.data when neither of the children is None.

I also suggest adding optional argument for children in method __init__, so that you can define a tree more easily.

Note that is_bst is a method of class Node. You called its first argument root, but we typically like to call the first argument of a method self. For instance, Node.is_bst(root.left) is equivalent to root.left.is_bst().

You don't really need to specify root: Node; of course root is of type Node; the first argument of at method of a class is always an object of that class.

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
    def is_bst(root):
        if root is None or (root.left is None and root.right is None):
            return True
        elif root.right is None:
            return root.left.data < root.data and root.left.is_bst()
        elif root.left is None:
            return root.right.data > root.data and root.right.is_bst()
        else:
            return (
                root.left.data < root.data < root.right.data
                and root.left.is_bst()
                and root.right.is_bst()
            )

a = Node(2, Node(4), Node(1))
b = Node(2, Node(1), Node(4))

print('a is a bst? ', a.is_bst())
# a is a bst?  False

print('b is a bst? ', b.is_bst())
# b is a bst?  True