class Solution {
private:
/// This mask is used to check the highest bit in a int number.
int mask = 1 << 31;
/// *code* is an int number that encodes the path to the leaf.
/// *counter* is the height of the full binary tree (upper n  1 levels).
bool check (TreeNode* root, int code, int counter) {
code <<= (32  counter);
while (counter > 0) {
/// When the highest code is 0, move to left. Otherwise move to left.
if (code & mask) root = root>right;
else root = root>left;
code <<= 1;
counter;
}
return root != nullptr;
}
public:
int countNodes(TreeNode* root) {
int counter = 0;
TreeNode *left = root, *right = root;
while (left && right) {
left = left>left;
right = right>right;
++counter;
}
if (counter == 0) return 0;
if (!left) return (pow(2, counter)  1);
/// leftcode encodes the path to the left most leaf (all 0s).
/// rightcode encodes the path to the right most (possible) leaf (all 1s).
int leftcode = 0, rightcode = 0;
for (int i = 0; i < counter; ++i) {
rightcode <<= 1;
rightcode += 1;
};
while (leftcode != rightcode && leftcode != rightcode  1) {
/// Get path to the middle leaf node.
int mid = leftcode + (rightcode  leftcode) / 2;
if (check(root, mid, counter)) leftcode = mid;
else rightcode = mid  1;
}
if (check(root, rightcode, counter)) return pow(2, counter) + rightcode;
else return pow(2, counter) + leftcode;
}
};
[O(log(n)^2) C++ Binary Search Method] Concise with explanation


Yes, this method has limitation  the height of this tree must be smaller than 32 (or we can use long to extend this limitation).
Time complexity of this method is O(log(n) * log(n))
 Need log(n) times to check the leaf node is null or not.
 For each check, we need O(height) = O(log(n)) moves along the tree.