# Python solution with detailed explanation

• Solution

Count Complete Tree Nodes https://leetcode.com/problems/count-complete-tree-nodes/?tab=Description

Algorithm

1. We need to use the idea of complete tree here.
2. Find the left depth (ld) and right depth (rd).
3. Only two cases are possible: ld == rd or ld > rd. rd can never be greater than ld because of the manner in which nodes are packed in the last level.
4. When ld == rd, then we are sure that left sub-tree is full. The right may or may not be full, but has same depth. Sketch a diagram to get the intuition.
5. When ld > rd, then we know that right subtree is full. Sketch a diagram to get the intuition.
6. Complexity: O(lgN * lgN) - There are lg(N) steps and in each step we do lg(N) work of finding the depth.
7. https://goo.gl/photos/eQJej6mGcToiRwGY6
``````class Solution(object):
def depth(self, root):
if not root:
return 0
return 1 + self.depth(root.left)

def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
l_d = self.depth(root.left)
r_d = self.depth(root.right)
if l_d > r_d:
return (2**r_d - 1) + self.countNodes(root.left) + 1
else:
return (2**l_d - 1) + self.countNodes(root.right) + 1
``````

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