Validate Binary Search Tree

Given the root of a binary tree, return true if it is a valid binary search tree: every node's left subtree holds only smaller values, its right subtree only larger values, and both subtrees are themselves valid BSTs.

Examples

in: root = [2,1,3]

out: true

valid

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

out: false

4 is in the right subtree of 5 but 3 < 5

Constraints

1 <= number of nodes <= 10^4
-2^31 <= node value <= 2^31 - 1

Hints

target: O(n) time⌘↩ run · ⇧⌘↩ submit