# 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).