Problem Link: https://leetcode.com/problems/count-complete-tree-nodes/description/

Target Time Complexity: O(log(n)), however in the worst case, which as per my understanding would be when last level has a single node, complexity would be O(n*log(n)). Kindly clarify.

There is a brute-force approach to counting the number of nodes in general, which is traversing through the entire tree and keeping count of the number of nodes encountered, which is O(n), where n is the number of nodes.

To improve on it, we could make use of the information that the tree is a complete binary tree and has O(log(n)) levels. So that we can compute left height and right height. In case these come out to be equal for a subtree root, then that subtree is a full binary tree and the number of nodes have a closed form solution as 2^h-1, where $h$ is the height of subtree.

In code, this would look something like:

int findLeftHeight(BinaryTreeNode<int>* root){
    int leftHeight = 0;
    while(root){
        leftHeight += 1;
        root = root->left;
    }
    return leftHeight;
}

int findRightHeight(BinaryTreeNode<int>* root){
    int rightHeight = 0;
    while(root){
        rightHeight += 1;
        root = root->right;
    }
    return rightHeight;
}

int countCompleteNodes(BinaryTreeNode<int>* root){
    if(root == NULL){
        return 0;
    }
    int lh = findLeftHeight(root);
    int rh = findRightHeight(root);

    if(lh == rh) return (1<<lh)-1;

    return 1 + countCompleteNodes(root->left) + countCompleteNodes(root->right);
}

But for the worst case, when the complete binary tree has just one node in the last level, with the number of levels being maximum permissible for the upper bound on n. Then it seems that the time it takes to count is O(n*log(n)), because at each recursive step we are making a call on both root->left and root->right. Kindly clarify. Thanks in anticipation.