What's the time complexity of this AC code?


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

  • 0
    B

    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.


  • 0
    R

    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?


  • 0
    A
    This post is deleted!

Log in to reply
 

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