Find `height`

of the tree and find the `m`

= height of `root->left`

(Right height of left subtree of Root)

if `m`

< `height`

, it means `right`

subtree of `root`

is a perfect tree of height `height-2`

. Add the no.of elements in this tree + 1(for root) into `count`

, and focus on the left half.

if `m`

>= `height`

, then `left`

subtree is perfect with a height of `height-1`

. Add no.of elements in this +1 to `count`

and focus on right half.

Decrement `height`

after every iteration as we step down.

```
int countNodes(TreeNode* root) {
if(!root)
return 0;
int count = 0, height=0,m;
TreeNode* temp = root;
while(temp){
++height;
temp=temp->left;
}
while(root){
m = 1;
temp=root->left;
while(temp){
++m;
temp=temp->right;
}
if(m<height){
count = count + (1<<(height-2));
root = root->left;
}
else{
count = count + (1<<(height-1));
root = root->right;
}
--height;
}
return count;
}
```

Outer loop runs till `root`

becomes `null`

. --> O(log n)

Inside we find height `m`

which takes --> O(log n)

Overal Complexity = `O(log n * log n)`