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.

Determine Whether a Binary Tree Is a Valid BST

Determine whether a compact breadth-first binary-tree encoding satisfies the strict binary-search-tree invariant. Every descendant must respect all ancestor bounds; duplicate values are invalid and an empty tree is valid.

Hints

1. Queue each existing node together with its open lower and upper bounds.
2. Avoid value plus or minus one so boundary integers remain safe.

Approach

Consume the compact encoding breadth first while carrying exclusive ancestor bounds with every existing node. Each non-None child must lie strictly within its derived interval.

• Time complexity: O(n)
• Space complexity: O(tree width)