Validate BST

Problem Statement

Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST). A valid BST must satisfy two conditions:

1. All nodes to the left of a node must have a value less than the node's value.
2. All nodes to the right of a node must have a value greater than the node's value.

Your task is to check if the given binary tree adheres to these conditions and return whether it is a valid BST or not.

Rules and Constraints

• The binary tree nodes are assumed to contain integer values.
• The tree is not necessarily balanced.
• No additional operations (e.g., insertion, deletion) are allowed on the tree.
• The function should return a boolean value indicating whether the tree is a valid BST.
• The solution should have a time complexity of O(n), where n is the number of nodes in the tree, since we need to visit each node exactly once.
• The solution should have a space complexity of O(h), where h is the height of the tree, due to the recursive call stack. In the worst case (when the tree is skewed), the height of the tree can be O(n).

Your task is to write a solution that meets these rules and constraints.

Example

Input: {"root":[2,1,3]} Output: true