Question: How would you validate a binary search tree (BST) using a recursive algorithm?

Answer:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def is_valid_bst(root):
    def is_valid(node, min_val, max_val):
        if not node:
            return True
        if node.value <= min_val or node.value >= max_val:
            return False
        return is_valid(node.left, min_val, node.value) and is_valid(node.right, node.value, max_val)
    
    return is_valid(root, float('-inf'), float('inf'))

# Example of usage
node1 = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_valid_bst(node1))  # Output: True

node2 = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
print(is_valid_bst(node2))  # Output: False

Explanation:

1. We define a TreeNode class to represent the nodes of the binary search tree.
2. We define the function is_valid_bst which takes the root node of the tree as the input and calls a helper function is_valid to perform the validation.
3. The is_valid function checks if a given node and its children satisfy the conditions of a BST.
4. It checks if the value of the current node falls within the range defined by min_val and max_val, and recursively validates the left and right subtrees by updating the range accordingly.
5. If any node violates the properties of a BST, the function immediately returns False. Otherwise, it returns True.
6. We then call the is_valid_bst function with a sample valid and invalid binary search tree to demonstrate its functionality.