Medium

Validate Binary Search Tree

021

Given a binary tree encoded as level-order with -100000 as null, return true if it is a valid BST.

EXAMPLES

Example 1

Input
{
  "root": [
    2,
    1,
    3
  ]
}

Output
true

FUNCTION SHAPE

root: intArray→bool

SOLUTION NOTE

Pass down constraints that get tighter as we go down. The invariant: isValid(node, min, max) is true iff node is a valid BST AND all values are within (min, max).

Reveal reference solution +

pythonREFERENCE

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    def isValid(root, lower_bound, upper_bound):
        if not root: return True

        return (lower_bound < root.val < upper_bound and
                isValid(root.left, lower_bound, root.val) and
                isValid(root.right, root.val, upper_bound))

    return isValid(root, float('-inf'), float('inf'))

TimeO(n)

SpaceO(h)

Open on LeetCode ↗