Try to solve the Validate Binary Search Tree problem.

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:

  • −104≤-10^{4} \leq Node.data ≤104\leq 10^{4}

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

Examples