π‘ 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.