Check if a binary tree satisfies the properties of a binary search tree.
- User
Check if a binary tree satisfies the properties of a binary search tree.
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: TrueExplanation:
-
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.
-
is_bst Function:
- Base Case: If the current node is
None, it returnsTruebecause 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_valueandmax_value. If not, it returnsFalse. - Recursive Check: It recursively checks the left subtree with the updated
max_valueset to the current node's value and the right subtree with the updatedmin_valueset to the current node's value.
- Base Case: If the current node is
-
Example Usage: The example constructs a binary tree and checks if it is a BST. The output will be
Trueif 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.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.