Validate Binary Search Tree

Statement

Given the root of a binary tree, check whether it is a valid binary search tree (BST).

A binary tree is a valid BST if for every node:

• The left subtree of a node contains only nodes with keys less than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.

• Both the left and right subtrees are valid BSTs.

Constraints:

• $-10^{4} \leq$ Node.data $\leq 10^{4}$

• The tree contains nodes in the range $[1, 500]$.

Examples