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 - 1root = [2,1,3]OutputtrueWhyEvery node satisfies the BST ordering rules, and both subtrees are valid.root = [5,1,4,null,null,3,6]OutputfalseWhyNode `3` appears in the right subtree of `5` but is less than `5`, so the tree is not a valid BST.root = [2,2,3]OutputfalseWhyThe left child equals the root, but BST values must be strictly smaller on the left.The number of nodes is in the range [0, 10^4]-2^31 <= Node.val <= 2^31 - 1Each node has fields val, left, and rightDuplicates are not allowed in a valid BSTdef is_valid_bst(root):
