```
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
// get height
int h = 0;
TreeNode p = root;
while (p.left != null) {
p = p.left;
h++;
}
// binary search on last level with bit manipulation approach
int lo = 0;
int hi = (1 << h) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int mask = 1 << h - 1;
TreeNode n = root;
for (int i = 0; i < h; i++) {
if ((mask & mid) == 0) {
n = n.left;
} else {
n = n.right;
}
mask >>= 1;
}
if (n == null) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo + (1 << h) - 1;
}
}
```