如何判断一棵树是否为二叉搜索树？及自定义BST判断算法返回结果异常的问题排查

Hey there! Let's tackle your two questions one by one, starting with the fundamentals and then fixing your code issue.

First, let's clarify the core rule of a Binary Search Tree (BST):
For every node in the tree:

• All nodes in its left subtree must have values less than the node's value
• All nodes in its right subtree must have values greater than the node's value
  (Note: Some definitions allow equal values in the right subtree or left subtree—adjust the logic based on your specific requirements.)

There are two reliable ways to check if a tree is a BST:

1. In-order Traversal Check #

A valid BST will produce a strictly increasing sequence (or non-decreasing, if duplicates are allowed) when traversed in-order. You can implement this by tracking the value of the previous node and comparing it to the current node during traversal. If any current node is not larger than the previous one, the tree isn't a BST.

2. Recursive Bound Check #

When recursively checking each node, pass along the allowed range of values it can take:

• The root node has no bounds (from -infinity to +infinity)
• A left child's maximum allowed value is its parent's value; its minimum remains the same as the parent's minimum
• A right child's minimum allowed value is its parent's value; its maximum remains the same as the parent's maximum
  If any node falls outside its allowed range, the tree isn't a BST.

Let's break down why your current code always returns True, even for tree2 which should fail:

Key Bugs in Your Code #

1. Wrong Attribute Name: Your Tree class stores node values in the entry attribute, but your code uses node.left.data and node.right.data—this should throw an AttributeError, but if you didn't hit that, it's likely a typo that needs fixing.
2. Incomplete Recursive Logic: You only check the direct parent-child value relationship, but you don't enforce that all nodes in a subtree follow the BST rules relative to ancestor nodes. For example, in tree2, the node 7 is in the right subtree of the root 12, so it should be greater than 12—your code only checks if 7 < 15 (its direct parent), missing this critical check.
3. Variable Name & Initialization Error: You tried to call is_BST_tree(t1) and is_BST_tree(t2) but never defined t1/t2—you need to build the tree instances using build_tree() first.

Fixed Code (Using Recursive Bound Check) #

class Tree():
    def __init__(self, entry, left=None, right=None):
        self.entry = entry
        self.left = left
        self.right = right
    def __repr__(self):
        if not self.left and not self.right:
            return "Tree({0})".format(repr(self.entry))
        return "Tree({0},{1},{2})".format(repr(self.entry), repr(self.left), repr(self.right))

def build_tree(tree):
    if tree:
        (entry, left, right) = (tree + (None, None))[:3]
        return Tree(entry, build_tree(left), build_tree(right))
    else:
        return None

def is_BST_tree(node, min_val=float('-inf'), max_val=float('inf')):
    # Empty node is valid
    if node is None:
        return True
    
    # Check if current node is within the allowed value range
    if not (min_val < node.entry < max_val):
        return False
    
    # Recursively check left and right subtrees with updated bounds
    return is_BST_tree(node.left, min_val, node.entry) and is_BST_tree(node.right, node.entry, max_val)

tree1 = (12, (6, (2,), (8,)), (15, (14,), (18,)))
tree2 = (12, (6, (2,), (8,)), (15, (7,), (20,)))

# Build the tree instances first
t1 = build_tree(tree1)
t2 = build_tree(tree2)

print(is_BST_tree(t1))  # Output: True
print(is_BST_tree(t2))  # Output: False

What Changed? #

• Added min_val and max_val parameters to enforce value ranges for each subtree
• Fixed the attribute name from data to entry
• Ensured we build the tree instances with build_tree() before validation
• The logic now checks that every node follows BST rules relative to all ancestors, not just its direct parent

Alternative: In-order Traversal Implementation #

If you prefer the in-order method, here's how you can write it:

def is_BST_tree_inorder(node):
    # Use a list to track the previous value (since lists are mutable in nested functions)
    prev_value = [float('-inf')]
    
    def inorder_traversal(current_node):
        if current_node is None:
            return True
        
        # Check left subtree first
        if not inorder_traversal(current_node.left):
            return False
        
        # Current node must be larger than the previous node in in-order traversal
        if current_node.entry <= prev_value[0]:
            return False
        
        # Update previous value to current node's entry
        prev_value[0] = current_node.entry
        
        # Check right subtree
        return inorder_traversal(current_node.right)
    
    return inorder_traversal(node)

# Test it
print(is_BST_tree_inorder(t1))  # True
print(is_BST_tree_inorder(t2))  # False

内容的提问来源于stack exchange，提问作者ahmed abu elvon