```
class Solution {
public:
int getHeight(TreeNode* u, int x, int ht) {
int height = 0;
int test = 1 << (ht - 1);
while (u) {
if ((test&x) == 0) u = u->left;
else u = u->right;
test >>= 1;
height++;
}
return height - 1;
}
int countNodes(TreeNode* root) {
TreeNode* u = root;
if(!u) return 0;
int height = 0;
while (u) {
u = u->left;
height++;
}
height--;
int left = 0, right = (1 << height) - 1;
while (left <= right) {
int mid = (left + right) >> 1;
int ht;
if (mid == 0)
ht = height;
else
ht = getHeight(root, mid, height);
if (height == ht) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return right + (1 << height);
}
```

};