# Python: fast O(log^2 n) = O(h^2) solution using binary search without recursion

• ``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def countNodes(self, root):
left_height = self.getLeftHeight(root)
right_height = self.getRightHeight(root)

if left_height == right_height:
return 2 ** left_height - 1
else:
return 2 ** (left_height - 1) - 1 + self.countLastRow(root, left_height, right_height)

def countLastRow(self, root, left_height, right_height):
count = 0

while left_height != right_height:
left_height -= 1
right_height -= 1
if self.getRightHeight(root.left) == right_height:
root = root.left
else:
count += 2 ** (left_height - 1)
left_height = self.getLeftHeight(root.right)
root = root.right

return count

def getLeftHeight(self, node):
height = 0
while node:
height += 1
node = node.left
return height

def getRightHeight(self, node):
height = 0
while node:
height += 1
node = node.right
return height``````

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