Find number of nodes in the complete binary tree

A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible

my first approach was to explore the tree using any tree traversal algorithm but time complexity is O(n).

I found an optimized solution that is based on a binary search approach. assume our tree looks like as shown in the figure so our goal is to find a node that marked the highest number.

now the first question is how to find a node exists or not in a complete binary tree.

Check 6 exist or not => binary representation of six is 110 . after removing the MSB bit, the string is 10. the resultant string we will use for choosing a direction either left or right. here 0 for left child and 1 for the right child. the time complexity is O(log(n)) for this step.

exist(6)?

let lower=1 and upper= 31 as the height of tree is 4 then the maximum possible number of nodes in a binary tree is 31.

mid=(lower+upper)/2=16 => check mid exist or not

exist(16)?

exist function return true so our expected answer is sixteen and then, we update lower to 17

mid=(lower+upper)/2=(17+31)/2=24

exist(24)?

24 does not exist in our tree so we update upper to 23.

mid=(lower+upper)/2=(17+23)/2=20

exist(20)?

twenty exist in the tree so lower update to 21 and answer changed to 20.

mid=(lower+upper)/2=(21+23)/2=22

exist(22)?

twenty-two does not exist in the tree so upper update to 21.

mid=(lower+upper)/2=(21+21)/2=21

exist(21)?

twenty-one exist in the tree so lower update to 22 and answer changed to 21.

so far lower=22, upper=21, ans=21 here we stop as lower exceed to the upper limit.

the answer is 21

the time complexity of the binary search is log(n) and for the above exist function it is log(n) so overall time complexity is log(n)*log(n).