# Determine Whether a Binary Tree Is a Valid BST ## Problem Given a binary tree, determine whether the entire tree satisfies the strict binary-search-tree invariant: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is 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 allowed in the input representation but make the result False. Empty trees return True. ## Constraints - The encoding contains at most 100,000 non-None nodes. - Values are signed integers and may equal the minimum or maximum value supported by the caller's integer type. - The represented structure is a tree with no cycles or shared child nodes. - The tree may be completely skewed. ## Examples tree = [2, 1, 3] output = True tree = [8, 3, 10, None, None, 6] output = False The second tree fails because 6 lies in the right subtree of 8. Checking only a node against its direct children would miss this violation. tree = [2, 2, 3] output = False ## Performance Goal Use O(n) time and avoid arithmetic such as value - 1 or value + 1 that can overflow at numeric boundaries. Discuss an iterative approach for a very deep tree.