# O(log^2(n)) using Binary Search, Python, Iterative

• 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 mid. We keep searching until we find the last not None leaf node, so we can know the size of the last level.

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``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.