**Solution**

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

**Algorithm**

- We need to use the idea of complete tree here.
- Find the left depth (ld) and right depth (rd).
- 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.
- 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.
- When ld > rd, then we know that right subtree is full. Sketch a diagram to get the intuition.
- Complexity: O(lgN * lgN) - There are lg(N) steps and in each step we do lg(N) work of finding the depth.
- 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
```