# Validate a Binary Search Tree ## Problem Given a binary tree, return whether it is a valid binary search tree. For every node, every value in its left subtree must be strictly smaller than the node's value, and every value in its right subtree must be strictly larger. Implement: def is_valid_bst(tree: list[int | None]) -> bool: ... ## Practice Input Representation To keep the exercise executable with literal/JSON test cases, the tree is represented by a breadth-first list named tree instead of custom node objects. This representation choice is a practice assumption; it does not change the underlying tree problem. - Each element is an integer value or None (JSON null) for a missing child. - The first element is the root. An empty list, or a list containing only None values, represents an empty tree. - Starting at the root, consume child slots breadth first: the next two entries are the left and right children of the next existing node. A None child creates no node and therefore consumes no child slots later. - If the list ends while child slots remain, all omitted trailing children are missing. - Extra trailing None values are harmless. A non-None value after no parent remains would be malformed; test inputs are guaranteed not to contain that case. - For example, [1, None, 2, 3] represents root 1, its right child 2, and node 2's left child 3. Duplicate values are valid input values but make the tree an invalid BST. Empty trees return True. ## Constraints - The encoding contains at most 100,000 non-None nodes. - Node values are signed integers and may be at numeric type boundaries. - The represented structure is a tree, not a graph; there are no cycles or shared child nodes. - The tree may be highly skewed. ## Examples tree = [2, 1, 3] output = True tree = [5, 1, 7, None, None, 4, 8] output = False The second tree is invalid because 4 is in the right subtree of 5 even though it is smaller than its direct parent 7. tree = [] output = True tree = [2, 2, 3] output = False ## Performance Goal Use O(n) time. Explain how the implementation handles a highly skewed tree without unsafe sentinel arithmetic.