# C++ 73ms.. beats 99.43% Based on binary search.

• 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)`

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.