```
def countNodes(self, root):
#recursive
def get_height(node):
count = 0
while node:
count += 1
node = node.left
return count
if not root:
return 0
left = get_height(root.left)
if get_height(root.right) == left:
return (1 << left) + self.countNodes(root.right)
else:
return (1 << (left - 1)) + self.countNodes(root.left)
def countNodes(self, root):
#iterative
def get_height(node):
count = 0
while node:
count += 1
node = node.left
return count
ans = 0
while root:
left = get_height(root.left)
if left == get_height(root.right):
ans += (1 << left)
root = root.right
else:
ans += (1 << (left - 1))
root = root.left
return ans
```