def countNodes(self, root):
if not root:
return 0
h1, h2 = self.height(root.left), self.height(root.right)
if h1 > h2: # right child is full
return self.countNodes(root.left) + 2 ** h2
else: # left child is full
return 2 ** h1 + self.countNodes(root.right)
# the height of the leftmost leaf node
def height1(self, root):
h = 0
while root:
h += 1
root = root.left
return h
def height(self, root):
if not root:
return 0
return self.height(root.left) + 1
Python O(lgn)*O(lgn) solution with comments.


Another idea: compute the depths of the leftmost node and rightmost node:
def countNodes(self, root): if not root: return 0 l = self.depthLeft(root.left) r = self.depthRight(root.right) if l == r: return 2**(l+1)  1 else: return 1 + self.countNodes(root.left) + self.countNodes(root.right) def depthLeft(self, node): d = 0 while node: d += 1 node = node.left return d def depthRight(self, node): d = 0 while node: d += 1 node = node.right return d