Check if a Binary Tree is a Binary Search Tree (BST)

Determining whether a given binary tree adheres to the rules of a Binary Search Tree (BST) is a common problem in computer science. A BST is a node-based binary tree data structure where each node has a value greater than all values in its left subtree and less than all values in its right subtree. This post will look at efficient Pythonic ways to solve this problem.

Understanding the Problem

Before diving into the code, let’s recap the defining characteristic of a BST:

• For every node in the tree:
  • The value of the node is greater than the value of every node in its left subtree.
  • The value of the node is less than the value of every node in its right subtree.

Recursive Approach

A recursive approach is often the most elegant and intuitive way to solve this problem. The function will recursively check each subtree to ensure they satisfy the BST property. We’ll use a helper function to pass along minimum and maximum bounds for each subtree.

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

def is_bst_recursive(node, min_val, max_val):
    """
    Recursively checks if a binary tree is a BST.

    Args:
        node: The root node of the subtree being checked.
        min_val: The minimum allowed value for nodes in this subtree.
        max_val: The maximum allowed value for nodes in this subtree.

    Returns:
        True if the subtree is a BST, False otherwise.
    """
    if node is None:
        return True

    if not (min_val < node.data < max_val):
        return False

    return (is_bst_recursive(node.left, min_val, node.data) and
            is_bst_recursive(node.right, node.data, max_val))

# Example usage:
root = Node(2)
root.left = Node(1)
root.right = Node(3)

print(f"Is the tree a BST? {is_bst_recursive(root, float('-inf'), float('inf'))}") #True


root2 = Node(5)
root2.left = Node(1)
root2.right = Node(4)
root2.right.left = Node(3)
root2.right.right = Node(6)

print(f"Is the tree a BST? {is_bst_recursive(root2, float('-inf'), float('inf'))}") #False

# Is the tree a BST? True
# Is the tree a BST? False

Iterative Approach (Using Inorder Traversal)

An alternative approach involves an inorder traversal of the tree. The inorder traversal of a BST will always produce a sorted sequence. We can use this property to check if the tree is a BST.

def is_bst_iterative(root):
    """
    Iteratively checks if a binary tree is a BST using inorder traversal.

    Args:
        root: The root node of the tree.

    Returns:
        True if the tree is a BST, False otherwise.
    """
    stack = []
    prev = float('-inf')

    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.data <= prev:
            return False
        prev = root.data
        root = root.right
    return True

#Example Usage (same trees as above)
print(f"Is the tree a BST? {is_bst_iterative(root)}") #True
print(f"Is the tree a BST? {is_bst_iterative(root2)}") #False

# Is the tree a BST? True
# Is the tree a BST? False

Both the recursive and iterative approaches provide efficient solutions to the problem of determining whether a given binary tree is a BST. The choice between them often comes down to personal preference and the specific context of the application. The recursive approach is generally easier to understand, while the iterative approach can be slightly more efficient in terms of memory usage for very large trees.