5 Best Ways to Check If a Binary Tree is a BST in Python

πŸ’‘ Problem Formulation: The task is to verify if a given binary tree adheres to the properties of a Binary Search Tree (BST). A BST requires that for any given node, the values in its left subtree are less than its own value and the values in the right subtree are greater. The input would be a binary tree, and the desired output is a boolean indicating whether or not the tree is a BST.

Method 1: In-Order Traversal Check

This method involves performing an in-order traversal of the binary tree and checking if the resulting list of node values is sorted in ascending order, which is a prerequisite for a BST. It’s a direct approach that leverages the BST property that an in-order traversal yields sorted values.

Here’s an example:

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

def is_bst_inorder(root):
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    return inorder(root) == sorted(set(inorder(root)))

# Assume this is our binary tree:
#     2
#    / \
#   1   3
# This should return True as this tree is a BST.

root = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_bst_inorder(root))

Output: True

The code defines a TreeNode class for the binary tree nodes and a function is_bst_inorder that checks for the BST property. The helper function inorder performs an in-order traversal. The function invocation returns True indicating the tree is a BST.

Method 2: Recursive Range Check

This method utilizes recursion to traverse the tree, confirming that each subtree adheres to the BST constraints by checking if the node values are within permitted ranges which get narrower as the recursion goes deeper into the tree.

Here’s an example:

def is_bst_recursive(node, min_val=float('-inf'), max_val=float('inf')):
    if not node:
        return True
    if not (min_val < node.val < max_val):
        return False
    return (is_bst_recursive(node.left, min_val, node.val) and
            is_bst_recursive(node.right, node.val, max_val))

root = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_bst_recursive(root))

Output: True

The is_bst_recursive function checks if a node’s value is within a valid range, narrowing this range as it checks each subsequent level through the tree. It returns True for our test case, indicating the tree satisfies BST properties.

Method 3: Iterative Traversal with Stack

Instead of recursion, this method performs an iterative in-order traversal. It uses a stack to explore the tree nodes while keeping track of the previous value to ensure the current one is greater, maintaining the BST property.

Here’s an example:

def is_bst_iterative(root):
    stack, prev = [], float('-inf')
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.val <= prev:
            return False
        prev = root.val
        root = root.right
    return True

root = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_bst_iterative(root))

Output: True

The function is_bst_iterative iterates through the tree, using a stack to keep track of nodes. It ensures each value it encounters is greater than the previous value, indicating the tree maintains BST order. The example returns True, confirming our sample tree is a BST.

Method 4: Morris In-Order Traversal

Morris In-Order Traversal is an efficient method that traverses a binary tree without recursion or a stack. Instead, it establishes temporary links back to the predecessors, thus saving space. This method can be adapted to verify BST property by ensuring that the values encountered are increasing.

Here’s an example:

def is_bst_morris(root):
    prev = None
    while root:
        if root.left is None:
            if prev and prev.val >= root.val:
                return False
            prev = root
            root = root.right
        else:
            pre = root.left
            while pre.right and pre.right is not root:
                pre = pre.right
            if pre.right is None:
                pre.right = root
                root = root.left
            elif pre.right is root:
                pre.right = None
                if prev and prev.val >= root.val:
                    return False
                prev = root
                root = root.right
    return True

root = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_bst_morris(root))

Output: True

The is_bst_morris function uses the Morris Traversal method, which saves space by not using extra data structures. Instead, it uses pointers to traverse the tree, validating the BST property at each step. The tree is confirmed BST when the output is True.

Bonus One-Liner Method 5: Short-Circuit In-Order Check

Applying Python’s generator functions and lazy evaluation, we can create a one-liner that aborts checking as soon as the BST property is violated during an in-order traversal. It’s a memory-efficient version of Method 1.

Here’s an example:

def is_bst_oneliner(node, min_val=float('-inf')):
    if node:
        if not all(is_bst_oneliner(node.left, min_val)):
            yield False
        if node.val <= min_val:
            yield False
        else:
            yield True
        yield from is_bst_oneliner(node.right, node.val)

root = TreeNode(2, TreeNode(1), TreeNode(3))
print(all(is_bst_oneliner(root)))

Output: True

This one-liner leverages generators for lazily checking BST properties. If a violation is detected, the generator yields False, short-circuiting further checks. Otherwise, it proceeds until it successfully verifies that the tree is indeed a BST.

Summary/Discussion

  • Method 1: In-Order Traversal Check. Strengths: Simple and intuitive. Weaknesses: Requires additional memory to store node values.
  • Method 2: Recursive Range Check. Strengths: Space efficient, leverages BST properties. Weaknesses: Recursive calls may lead to stack overflow for deep trees.
  • Method 3: Iterative Traversal with Stack. Strengths: Avoids recursion issues, works well for deep trees. Weaknesses: Requires extra space for the stack.
  • Method 4: Morris In-Order Traversal. Strengths: Space efficient as it doesn’t use extra space for stack or recursion. Weaknesses: Modifies the tree during the traversal, which might not be acceptable in all use cases.
  • Method 5: One-Liner Short-Circuit Check. Strengths: Elegant and memory-efficient. Weaknesses: Not as readable as other methods, which may reduce maintainability.