💡 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.