Idea is simple:

Firstly, I get the max depth of the tree by going to the left most node (d);

Then, I binary search the right-most node that exist in the d-th level (check function returns whether there is the m-th node in the d-th level).

```
class Solution(object):
def check(self, root, m, d):
if root == None:
return False
elif d == 0:
if root.left == None and root.right == None:
return True
if m > 2**(d - 1):
return self.check(root.right, m - 2**(d - 1), d - 1)
else:
return self.check(root.left, m, d - 1)
def countNodes(self, root):
n, d = root, -1
while n != None:
d += 1
n = n.left
l, r = 1, 2**d
while l < r:
m = (l + r + 1)/2
if self.check(root, m, d):
l = m
else:
r = m - 1
return l + 2**d - 1 if d >= 0 else 0
```