# What's the time complexity of this AC code?

• ``````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);
}
};``````

• I think average case it is O(nlogn), and worst case (ie for a skewed tree) it is O(n2).
You are calling isValidBst() once per node, and for each of those calls you are doing a height traversal (ie O(log(n)) for avg case, and O(n) for worst case).

There's a linear time solution where you recursively traverse down the tree, passing a 'min' and a 'max' allowed value for each node.

• good, I have implemented the code that you say, it's linear exactly.
I think it is sigma(i* lgi) i=1->n similar summation for this code, but ususally, I often do not know how to get the time complexity, especially recursive code, I only know using recursive equation to compute, could you help me in this area?

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.