Why this code runs extremely slow on OJ, compared to the O(N^2) solution?


  • 0
    B

    The following solution was I learned from the discussion trying to refine my code, however, I don't understand why it runs much slower than the common O(N^2) solution, which recursively calls depth and isBalanced. Thank you so much!
    class Solution {
    public:

    int height(TreeNode* root){
        if(root == NULL){
            return 0;
        }
        int left = height(root -> left);
        if(left == -1){
            return -1;
        }
        int right = height(root -> right);
        if(right == -1){
            return -1;
        }
        if(abs(left - right) > 1){
            return -1;
        }
        return max(height(root -> left), height(root -> right)) + 1;
    }
    
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
    

    };


  • 1

    What's the common O(N^2) solution? Can you show one?

    Your own is only quadratic or maybe worse, not sure. Trivial to make it the common O(N), though. Just think about your last line in your height function.


  • 0
    B

    I think the last line of my height function should be modified to "return max(left, right) + 1", that would be better...
    Thank you so much for pointing it out!
    By the common solution, I meant the following kind of method:

    int height(TreeNode* treenode){

        if(treenode == NULL){
            return 0;
        }
    
        return max(height(treenode->left), height(treenode->right)) + 1;
    }
    
    bool isBalanced(TreeNode* root) {
        if(!root){
            return true;
        }
        if(abs(height(root->left), height(root->right)) <= 1 
        && isBalanced(root->left) 
        && isBalanced(root->right)){
            return true;
        }
        return false;
    }

  • 0

    About yours: Yes, just don't recompute the values you already have.

    About the other one: What's a worst case input for that method? I don't see O(N^2) being tight. For a complete tree it's O(NlogN) and for a "line tree" (like only going left) it's O(N). Is there actually something worse in between these two extremes?


  • 0
    B

    Thanks a lot! I think I need to learn more about algorithm analysis, I am a novice now... Thank you again for your explanation!


Log in to reply
 

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