Validate Binary Search Tree

Problem

Check whether a binary tree given in level order is a valid binary search tree.

tree is a list in LeetCode-style level order where None marks a missing node; the children of index i are at 2*i + 1 and 2*i + 2. A valid BST requires every node in the left subtree to be strictly smaller and every node in the right subtree strictly larger.

Return True if valid, otherwise False. An empty tree is valid.

Hint

Pass down an allowed (low, high) interval for every node instead of only comparing with the parent.

Test cases

case 1

in: [[2,1,3]]

expected: true

case 2

in: [[5,1,4,null,null,3,6]]

expected: false

case 3

in: [[]]

expected: true

case 4

in: [[1,1]]

expected: false

case 5

in: [[10,5,15,3,7,null,18]]

expected: true

Starter codePython

def is_valid_bst(tree):
    # Your code here
    pass

5 test cases · run your code against them in the editor