I want to know the complexity of the algorithm, O(logN * logN)?


  • 0
    E
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        int lnum = 0;
        for(TreeNode* p=root; p!=nullptr; p=p->left)
            ++lnum;
        int rnum = 0;
        for(TreeNode *p=root; p!=nullptr; p=p->right)
            ++rnum;
        if(lnum == rnum) return (1<<lnum)-1;
        if(rnum == 1) return 2;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }

  • 1
    L

    OK. This one really threw me off when I first read the solution. But if you pay attention to the property of complete trees, at most one of the two subtrees will be incomplete. For a complete tree, the run time is the height of the tree, that is, log(n). Then we are done. If one of its two subtrees is not complete, the run time on the complete subtree will be log(n/2), and we recurse on that incomplete subtree whose size of is roughly n/2. Therefore even though we have countNodes(leftTree) + countNode(rightTree) at the end, because of the special property of complete tree, this is really only one CountNode() call to the incomplete tree plus log(n/2) for the complete tree.

    The recursion is T(n) = T(n/2) + O(log(n/2)) + O(log(n)).

    The T(n/2) is for the incomplete subtree, log(n/2) is for the complete subtree and log(n) is the time taken by the two for loops that walk down to the left most and right-most tree. The above recursion can be written as
    T(n) = T(n/2) + O(log(n)). Referring to Master theorem, the running time is O(logN * logN)


  • 0

    GREAT! Thank you. I was going crazy.


Log in to reply
 

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