0. Problem

To solve this problem, you can realize that inorder traversals visit values in a BST from smallest to largest (like in the last problem). If the inorder traversal visits nodes in increasing order, then the tree is a BST. Otherwise it's not a BST.

1. Recursion

The recursion for an inorder traversal is this:

def inorder(node):

    inorder(node.left)
    # check the values are in increasing order
    inorder(node.right)

2. Base case

The inorder traversal should stop when it gets to a node that's null. It should also stop if we know the tree is not a BST since there's no point in continuing.

if not node or not isBST:
    return # do nothing

3. Code

To code the solution, we just combine the recursion and base case.

def isBinarySearchTree(root):

    prev = float('-inf') # previous node value
    isBST = True # assume tree is a BST until we find it's not

    def inorder(node):
        nonlocal isBST, prev
        if not node or not isBST:
            return

        inorder(node.left)

        # check that the values are increasing
        # if they're not, set isBST to False
        # after visiting the node, set prev = node
        if not (prev < node.val):
            isBST = False
        prev = node.val

        inorder(node.right)

    inorder(root)
    return isBST

Time Complexity $O(n)$. We visit every node in the tree.

Space Complexity $O(n)$. The Call Stack takes O(n) memory.

0. Problem

Every time we move left in the BST, the values have to be lower than the parent value, which we'll call high. And every time we move right, the values have to be higher than the parent value, which we'll call low.

Here's an example:

To solve this problem, we want to make a function that checks if the tree is valid. It needs to have low and high as inputs.

isBST(node, low, high)

1. Recursion

A node is a BST if it's value is between low and high, and if its children are BSTs.

isBST(node, low, high) = {
    low < node.val < high
    and isBST(node.left, low, node.val) # if step left, then `high=node.val`
    and isBST(node.right, node.val, high) # if step right then `low=node.val`
}

2. Base case

Eventually, the recursion gets to a node that's null. In this case, a null node is a valid BST.

if node is None:
    return True

3. Code

To code this up, just combine the recursion and base case.

def isBinarySearchTree(root):
    def isBST(node, low, high):
        # base case
        if node is None:
            return True
        
        # recursion
        return (
            low <= node.val <= high
            and isBST(node.left, low, node.val)
            and isBST(node.right, node.val, high)
        )

    return isBST(root, float('-inf'), float('inf'))

Time Complexity $O(n)$. We step through every node in the tree.

Space Complexity $O(n)$. The Call Stack might get $n$ calls deep if the tree is unbalanced.