Idea is pretty much the same as the way binary search works:

###Search if the right most child node exists in left sub-tree

If it exists, that means the left sub-tree is a perfect binary tree, so just add up those nodes by simple math and go to unfinished subtree, a.k.a, right sub-tree.

if not, that also means the right sub-tree will def have one level less than tree height, also apply simple math to this and keep digging into left-subtree until a perfect binary tree is found.

```
def hasFullNodes(root, depth):
ptr = root
for i in xrange(depth):
if ptr is None:
return False
ptr = ptr.right
return True
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
if root.left is None:
return 1
if root.right is None:
return 2
ptr, depth = root, 0
while ptr is not None:
ptr = ptr.left
depth += 1
ptr = root
count = 0
for i in xrange(depth-1, 0, -1):
left, right = ptr.left, ptr.right
if hasFullNodes(left, i):
count += (2 ** i) - 1
ptr = right
else:
count += 2 ** (i-1) - 1
ptr = left
count += 1 # ptr
if i == 1 and ptr is not None:
count += 1 # Corner case
return count
```