# Leetcode 222 - Count Complete Tree Nodes

### Understanding the problem

The problem statement on LeetCode reads as follows:

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: root = [1,2,3,4,5,6]

Output: 6

We can use binary search to find the number of nodes in the tree because the tree is a complete binary tree, which means that the nodes are filled in level by level from left to right. This means that we can use the height of the left subtree to calculate the number of nodes in the tree using binary search.

First, we calculate the height of the left subtree. Then, we set the left and right pointers to the minimum and maximum possible values for the index of a node in the tree (1 and 2^h-1, respectively). We use the `exists()` function to check if the node at index mid exists in the tree. If it exists, we move the left pointer.

Now that we have a plan, let’s implement it in Python.

``````def countNodes(root):
# Base case: if the root is None, return 0
if not root:
return 0

# Calculate the height of the left subtree
h = 0
node = root
while node:
h += 1
node = node.left

# Calculate the number of nodes in the tree using binary search
left, right = 1, 2**h - 1
while left <= right:
# Calculate the middle point between the left and right pointers
mid = (left + right) // 2
# Check if the node at index mid exists in the tree
if exists(root, h, mid):
# If it exists, move the left pointer to the middle point
left = mid + 1
else:
# If it does not exist, move the right pointer to the middle point
right = mid - 1

# Return the number of nodes
return 2**h - 1 + left - 1

def exists(root, h, index):
# Base case: if the root is None, return False
if not root:
return False

# Calculate the height of the right subtree
h_right = 0
node = root
while node:
h_right += 1
node = node.right

# If the height of the right subtree is equal to h-1, it means that the left subtree is a full tree
if h_right == h - 1:
# If the index is in the left subtree, recurse on the left child
if index <= 2**(h-1) - 1:
return exists(root.left, h-1, index)
# If the index is in the right subtree, recurse on the right child
else:
return exists(root.right, h-1, index - 2**(h-1))
# If the height of the right subtree is less than h-1, it means that the right subtree is a full tree
else:
# If the index is in the left subtree, recurse on the left child
if index <= 2**h_right - 1:
return exists(root.left, h_right, index)
# If the index is in the right subtree, recurse on the right child
else:
return exists(root.right, h_right, index - 2**h_right)
``````