```
class Solution {
public:
bool isValidBST(TreeNode *root) {
if(!root) return 1;
TreeNode* p=root->left, *q=root->right;
while(p && p->right) p=p->right;
while(q && q->left) q=q->left;;
return isValidBST(root->left) && isValidBST(root->right) && (!p || p->val < root->val) && (!q || q->val > root->val);
}
};
```

in my opinion, maybe it's not linear, could anyone tell me ?

Thanks.

I thinks exists linear time code with recursive solution, instead of inorder travesal

Thanks for BIgO's help

Below is ON solutoin

```
class Solution {
public:
bool isValidBST(TreeNode *root) {
int maxn=0, minn=0;
return f(root, maxn, minn);
}
bool f(TreeNode* root, int& maxn, int &minn)
{
if(!root)
{
maxn=INT_MIN;
minn=INT_MAX;
return 1;
}
int leftmaxn=0, leftminn=0, rightmaxn=0, rightminn=0;
bool leftBST=f(root->left, leftmaxn, leftminn);
bool rightBST=f(root->right, rightmaxn, rightminn);
maxn=max(max(leftmaxn, rightmaxn), root->val);
minn=min(min(leftminn, rightminn), root->val);
return leftBST && rightBST && (!root->left || root->val>leftmaxn) && (!root->right || root->val < rightminn);
}
};
```