💡 Problem Formulation: This article dives into the challenge of determining whether a Binary Search Tree (BST) is embedded within a given Binary Tree (BT) using Python. The task requires an algorithm that identifies the BST structure amongst the nodes of a larger, unsorted BT. The input would be a constructed BT, and the output would be a boolean value indicating the presence or absence of a BST.
Method 1: Recursive Subtree Verification
This approach involves checking every subtree in the binary tree to find if it satisfies BST properties. The recursive function will be invoked for every node, and it will determine if the subtree rooted at that node is a BST by comparing node values for the BST property: left child < parent < right child.
Here’s an example:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_bst(node, min_val=float('-inf'), max_val=float('inf')):
if not node:
return True
if not min_val < node.value < max_val:
return False
return is_bst(node.left, min_val, node.value) and is_bst(node.right, node.value, max_val)
# Example usage
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
print(is_bst(root)) Output will be: True
This code snippet defines a function is_bst(), which recursively checks if a subtree is a BST. It does this by passing down minimum and maximum values that a node must be between to be considered valid. The root node is checked against negative and positive infinity since it has no constraints. If all nodes satisfy the BST requirement, True is returned.
Method 2: In-Order Traversal Check
In-order traversal of a BST yields a sorted sequence of values. This method performs in-order traversal of the binary tree and stores the node values. The method then checks if the stored values are sorted, which would imply the presence of a BST.
Here’s an example:
def in_order_traversal(node, result=None):
if result is None:
result = []
if node:
in_order_traversal(node.left, result)
result.append(node.value)
in_order_traversal(node.right, result)
return result
# Example usage
in_order_result = in_order_traversal(root)
print(in_order_result == sorted(in_order_result))Output will be: True
The code defines the function in_order_traversal() which traverses the tree in in-order fashion and appends the node values to the result list. After traversal, it checks if the list is equal to its sorted version – which verifies the BST property.
Method 3: Dynamic Programming on Subtrees
This more advanced approach employs dynamic programming to store results of BST checks on subtrees. By caching these results and reusing them, we avoid redundant computations and improve efficiency. This is particularly useful for large trees.
Here’s an example:
def check_subtrees(node, cache=None):
if cache is None:
cache = {}
if node in cache:
return cache[node]
if is_bst(node):
cache[node] = True
return True
cache[node] = check_subtrees(node.left, cache) or check_subtrees(node.right, cache)
return cache[node]
# Example usage
print(check_subtrees(root))Output will be: True
The check_subtrees() function uses a cache to remember results of BST checks on subtrees. When a node is determined to be the root of a BST, it’s stored in the cache. The cache is then used to quickly resolve future queries without recalculating.
Method 4: Iterative Depth-First Search
This approach entails an iterative depth-first search (DFS) with stack usage. We traverse the tree depth-first while checking the BST property. This method uses iterative stack manipulation instead of system stack via recursion.
Here’s an example:
def iterative_dfs(root):
stack = [(root, float('-inf'), float('inf'))]
while stack:
node, lower, upper = stack.pop()
if not node:
continue
val = node.value
if val <= lower or val >= upper:
return False
stack.append((node.right, val, upper))
stack.append((node.left, lower, val))
return True
# Example usage
print(iterative_dfs(root))Output will be: True
The iterative_dfs() function uses a stack to implement a DFS. The triplets in the stack contain node references and their value range constraints. If a node violates its constraints, it indicates that a BST isn’t present.
Bonus One-Liner Method 5: Using Library Function
In practice, a Python library like bst-checker (hypothetical) could potentially provide a ready-to-use function that implements any of the above methods with optimizations.
Here’s an example:
from bst_checker import is_tree_bst # Example usage print(is_tree_bst(root))
Output will be: True
This is a hypothetical example assuming the existence of a library function called is_tree_bst() which checks for the BST property in a binary tree. This single line of code would replace our custom implementations for simplicity.
Summary/Discussion
- Method 1: Recursive Subtree Verification. Strong because of its simplicity; weaknesses include heavy recursion overhead for large trees.
- Method 2: In-Order Traversal Check. Good for understanding the BST property through in-order sorting. Not the most space-efficient method due to the need to store the entire traversal.
- Method 3: Dynamic Programming on Subtrees. Efficient for larger trees by reducing redundant computations through caching; however, it may require a significant amount of memory for the cache.
- Method 4: Iterative Depth-First Search. Robust against deep trees where recursion could lead to stack overflow. More complex to understand and implement.
- Method 5: Using Library Function. The easiest and most practical method if such a library function exists. The disadvantage may be less control over algorithm details and potential difficulty debugging.