Optimally counting number of nodes in a complete binary tree

Question

I am looking at LeetCode problem 222. Count Complete Tree Nodes:

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

I am targeting time complexity O(log(n)), however in the worst case, which as per my understanding would be when the last level has a single node, the complexity would be O(n*log(n)). But this would not meet the required "less than O(n)". What am I missing here?

Analysis

The 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, 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.

What am I missing here?

Have you properly benchmarked your optimization to use the findLeftHeight/findRightHeight stuff? I'm not convinced it's actually faster in the best or general case. — selbie
– selbie, Commented Jun 22, 2024 at 8:42
Target time complexity is less than O(n) not O(log(n)), so O(log(n)^2) would count for example. — john
– john, Commented Jun 22, 2024 at 8:42
At least one of the child is complete, so "real" recursion in only done in one child. — Jarod42
– Jarod42, Commented Jun 22, 2024 at 9:42

trincot · Accepted Answer · 2024-06-22 10:22:26Z

1

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.

But realise that at least one of these two recursive calls will have lh == rh. It cannot happen that this is false for both subtrees, as that would imply the binary tree is not a complete one. For instance, it would be false for both subtrees 𝐴 and 𝐵 here:

              _ * _
             /     \
            A       B
           / \     / \
          *   *   *   *
         / \     /
        *   *   *

...which is not a complete binary tree.

Concluding, although two recursive calls are made, we can be sure that at least one of them will not have any deeper recursive calls, so it will execute with O(1) time complexity. The remaining one might have deeper recursive calls, but always along one path, narrowing down to the spot where the bottom layer has its rightmost leaf.

answered Jun 22, 2024 at 10:22

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Paras Khosla Over a year ago

Alright so that means that eventually we will end up performing O(log(n)) calls on roughly the height of the tree, which means this is O((log(n))^2).

trincot Over a year ago

Yes, and that is sub-linear.

Collectives™ on Stack Overflow

Optimally counting number of nodes in a complete binary tree

Analysis

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Analysis

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related