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