# Python O(lgn)*O(lgn) solution with comments.

• ``````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 left-most 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``````

• Another idea: compute the depths of the left-most node and right-most 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``````

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