The key idea of this binary search approach is to search in the last level of the tree.

If the ** mid** of the last level is not None, then the size of last level is at least

**. We keep searching until we find the last not None leaf node, so we can know the size of the last level.**

*mid*To get to the Kth node in the last level, I use the binary representation of K to track the path from root to leaf. If current bit is '1' then turn the right child, else turn right.

```
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
height = self.getHeight(root)
last_level = 0
left, right = 0, 2**height-1
while left <= right:
mid = (left+right)/2
if self.getKthNode(root, height, mid) is None:
right = mid - 1
else:
left = mid + 1
last_level = mid+1
return last_level + 2**height - 1
def getHeight(self, root):
count = 0
while root.left is not None:
count += 1
root = root.left
return count
def getKthNode(self, root, height, k):
# binary bits representation of the root-to-leaf path
while height > 0:
if 2**(height-1) & k == 2**(height-1): # current bit is '1', turn right
root = root.right
else: # current bit is '0', turn left
root = root.left
height -= 1
return root
```