At Dropbox, a service stores ordered values in a binary tree and needs to verify that the structure satisfies binary search tree rules. Given the root of a binary tree, implement a function that returns True if it is a valid binary search tree (BST), otherwise return False.
A valid BST must satisfy all of the following:
root, the root node of a binary tree represented as nested dictionaries or null.Example 1
Input: root = {"val": 2, "left": {"val": 1, "left": null, "right": null}, "right": {"val": 3, "left": null, "right": null}}
Output: true
Explanation: Every node satisfies the BST ordering constraints.
Example 2
Input: root = {"val": 5, "left": {"val": 1, "left": null, "right": null}, "right": {"val": 4, "left": {"val": 3, "left": null, "right": null}, "right": {"val": 6, "left": null, "right": null}}}
Output: false
Explanation: The node with value 4 is in the right subtree of 5 but is less than 5, so the tree is not a valid BST.
[0, 10^4]-2^31 <= node.val <= 2^31 - 1root = {"val": 2, "left": {"val": 1, "left": null, "right": null}, "right": {"val": 3, "left": null, "right": null}}OutputtrueWhyThe left child is less than 2 and the right child is greater than 2, so the tree satisfies BST rules.root = {"val": 5, "left": {"val": 1, "left": null, "right": null}, "right": {"val": 4, "left": {"val": 3, "left": null, "right": null}, "right": {"val": 6, "left": null, "right": null}}}OutputfalseWhyAlthough 4 is the right child of 5, it is smaller than 5, which violates the BST property.root = {"val": 5, "left": {"val": 4, "left": null, "right": null}, "right": {"val": 6, "left": {"val": 3, "left": null, "right": null}, "right": {"val": 7, "left": null, "right": null}}}OutputfalseWhyThe node 3 is in the right subtree of 5, so it must be greater than 5, but it is not.The number of nodes is in the range [0, 10^4]-2^31 <= node.val <= 2^31 - 1Each node has fields: val, left, and rightA valid BST requires strict ordering: left < node < rightdef is_valid_bst(root):
