Skip to content
TheChatArchiveThe Chat Archive
Mistralmistral-small-3.1-24b-instruct-2503· Mistral AIHugging Face LMArena Human Preference 140K

Check if a binary tree satisfies the properties of a binary search tree.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Geminigemini-2.5-flash’s answer.
  1. User

    Check if a binary tree satisfies the properties of a binary search tree.

  2. Mistral Assistant

    To check if a binary tree satisfies the properties of a binary search tree (BST), you need to ensure that for every node in the tree, the values in the left subtree are less than the node's value, and the values in the right subtree are greater than the node's value. Here is a Python function to perform this check using a recursive approach:

    class TreeNode:
        def __init__(self, value=0, left=None, right=None):
            self.value = value
            self.left = left
            self.right = right
    
    def is_bst(node, min_value=float('-inf'), max_value=float('inf')):
        """
        Check if the binary tree rooted at 'node' is a binary search tree.
    
        Args:
            node (TreeNode): The root of the binary tree to check.
            min_value (float): The minimum value that the node can have.
            max_value (float): The maximum value that the node can have.
    
        Returns:
            bool: True if the tree is a BST, False otherwise.
        """
        if node is None:
            return True
    
        # Check if the current node's value is within the valid range
        if node.value <= min_value or node.value >= max_value:
            return False
    
        # Recursively check the left and right subtrees
        return (is_bst(node.left, min_value, node.value) and
                is_bst(node.right, node.value, max_value))
    
    # Example usage:
    # Constructing a binary tree
    #        10
    #       /  \
    #      5    15
    #     / \   / \
    #    3   7 12  20
    
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(15)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(7)
    root.right.left = TreeNode(12)
    root.right.right = TreeNode(20)
    
    # Check if the tree is a BST
    print(is_bst(root))  # Output: True
    

    Explanation:

    1. TreeNode Class: This class defines the structure of a node in the binary tree. Each node has a value, a left child, and a right child.

    2. is_bst Function:

      • Base Case: If the current node is None, it returns True because an empty tree is considered a BST.
      • Value Check: It checks if the current node's value is within the valid range defined by min_value and max_value. If not, it returns False.
      • Recursive Check: It recursively checks the left subtree with the updated max_value set to the current node's value and the right subtree with the updated min_value set to the current node's value.
    3. Example Usage: The example constructs a binary tree and checks if it is a BST. The output will be True if the tree satisfies the BST properties.

    This approach ensures that each node is checked against the correct range of values, maintaining the properties of a binary search tree.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.