# My Python solution with O(h^2) time complexity

• Idea is pretty much the same as the way binary search works:
###Search if the right most child node exists in left sub-tree
If it exists, that means the left sub-tree is a perfect binary tree, so just add up those nodes by simple math and go to unfinished subtree, a.k.a, right sub-tree.

if not, that also means the right sub-tree will def have one level less than tree height, also apply simple math to this and keep digging into left-subtree until a perfect binary tree is found.

``````def hasFullNodes(root, depth):
ptr = root
for i in xrange(depth):
if ptr is None:
return False
ptr = ptr.right
return True

class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
if root.left is None:
return 1
if root.right is None:
return 2

ptr, depth = root, 0
while ptr is not None:
ptr = ptr.left
depth += 1
ptr = root
count = 0
for i in xrange(depth-1, 0, -1):
left, right = ptr.left, ptr.right
if hasFullNodes(left, i):
count += (2 ** i) - 1
ptr = right
else:
count += 2 ** (i-1) - 1
ptr = left
count += 1 # ptr
if i == 1 and ptr is not None:
count += 1 # Corner case
return count``````

• Why it is O(h) rather than O(h^2)?

• true. Forgot to add up `hasFullNodes` complexity. Thanks for the heads up!

• Not a problem. I am thinking about if an O(h) algorithm would possibly exist. Do you think if you solution can be optimized to O(h)?

• Beats me, can't think of `O(h)` solutioin...

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