At Stripe, a service stores ordered values in a binary tree and needs to verify that the structure is a valid binary search tree (BST). Write a function that returns True if the tree is valid and False otherwise.
A binary tree is a valid BST if, for every node:
root, the root node of a binary tree. Each node has fields val, left, and right.Example 1
root = [2,1,3]true1 < 2 < 3, and both subtrees satisfy BST rules.Example 2
root = [5,1,4,null,null,3,6]false4 is to the right of 5, its left child 3 is also in the right subtree of 5 and must be greater than 5, which it is not.[0, 10^4]-2^31 <= Node.val <= 2^31 - 1