```
bool leafExist(TreeNode *root, int test, int n) {
TreeNode *node = root;
for (int i =n-2;i >= 0;i--)
if ((1 << i) & test)
node = node->right;
else
node = node->left;
return node != nullptr;
}
int countNodes(TreeNode* root) {
if (!root) return 0;
int n = 0;
TreeNode *node = root;
while (node) {
node = node->left;
++n;
}
if (n == 1) return 1;
int start = 0, end = (1<<(n-1)) - 1, mid;
int minus = 0;
if (!leafExist(root,end,n)) {
while (start != end - 1) {
mid = (start+end)/2;
if (leafExist(root,mid,n)) {
start = mid;
} else {
end = mid;
}
}
minus = (1<<(n-1)) - end;
}
return (1<<n) - 1 - minus;
}
```