Problem

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:

1. Every node in the left subtree contains a value strictly less than the current node's value.
2. Every node in the right subtree contains a value strictly greater than the current node's value.
3. Both left and right subtrees must also be valid BSTs.

Formal Specification

• Input: root, the root node of a binary tree represented as nested dictionaries or null.
• Output: A boolean indicating whether the tree is a valid BST.

Examples

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.

Constraints

• Number of nodes is in the range [0, 10^4]
• -2^31 <= node.val <= 2^31 - 1
• Node values must be compared using strict inequality