# Python solution that finds the path of last leaf node in the complete binary tree

• The basic idea is to track the path of the last node in a complete binary tree.
For example, if the tree is:

``````     1
2     3
4   5
``````

Then the last leaf node is 5, so to track its path, with '0' representing go to the left child and '1' representing go to the right child, the consequence path is '001'. Such path has two meanings:

1. the tree height;
2. its int value + 1 = its position in the last level.
And therefore, the total count of nodes can be calculated.
``````    def countNodes(self, root):
if root is None:
return 0
if self.isComplete(root):
return 2 ** (self.rightHeight(root) + 1) - 1
mid = root
path = '0'

while not self.isComplete(mid):
l = mid.left
r = mid.right
if self.isComplete(l):
if self.isComplete(r):
mid = l
path += '0' + ('1' * self.rightHeight(mid))
else:
mid = r
path += '1'
else:
mid = l
path += '0'
return 2 ** (len(path) - 1) + int(path, 2)

def isComplete(self, node):
return self.leftHeight(node) == self.rightHeight(node)

def leftHeight(self, node):
if node is None:
return 0
count = 0
while node.left:
node = node.left
count += 1
return count

def rightHeight(self, node):
if node is None:
return 0
count = 0
while node.right:
node = node.right
count += 1
return count
``````

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