Validate BST

Python data engineering interview problem. Difficulty: advanced. Pattern: Trees. About 18 minutes. Part of the Pro drill bank.

Check whether a level-order tree is a valid BST. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A search tree is only useful when every node stays inside the bounds set by its ancestors. Checking only each node against its direct child can miss a deeper violation. Return whether the level-order tree satisfies the BST rule: every value in a left subtree is smaller and every value in a right subtree is larger. Write is_valid_bst(level_order: list) -> bool. [2, 1, 3] has 1 on the left and 3 on the right, so it is valid. The starter file already has the function name and harness print lines. Keep them and fill only the function body.

Requirements

• Carry lower and upper bounds through the tree.
• Reject a value outside its full ancestor range.
• Return a boolean.

Constraints

• The tree uses None for missing nodes and BST values are strictly ordered.
• The return type is bool.

Examples

Input: is_valid_bst([2, 1, 3]) Output: True Classic valid BST.

Topics: lakebench, python, bst, bounds.

More Python interview questions · All interview problems · Learn data engineering