Problem Overview

You are given the root of a complete binary tree, and your task is to count the total number of nodes present in the tree.

A complete binary tree is a special type of binary tree where:

• Every level, except possibly the last, is completely filled.
• All nodes in the last level are as far left as possible.

Your goal is to determine the total number of nodes efficiently without performing a simple traversal that visits every node.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

---

Intuition and Approach

A simple recursive or BFS traversal that visits every node would give the count directly, but it would take O(n) time, which is inefficient for large trees.
However, because this is a complete binary tree, we can exploit its structure to reduce the complexity.

Key insight:
In a complete binary tree,

• The height of the left subtree and the height of the right subtree can help determine if one of the subtrees is a perfect binary tree.
• A perfect binary tree of height h has exactly (2^h) - 1 nodes.

We can use this property recursively to skip counting entire perfect subtrees in constant time.

---

Step-by-Step Approach

1. Base Case
   • If the root is null, there are no nodes, so return 0.
2. Find the Left Height and Right Height
   • Compute the height by moving down the leftmost path (for left height) and rightmost path (for right height).
   • Let leftHeight = height of the left subtree.
   • Let rightHeight = height of the right subtree.
3. If Left Height == Right Height
   • This means the tree is a perfect binary tree.
   • Number of nodes = (2^height) - 1.
4. If Left Height != Right Height
   • The tree is not perfect, so we count recursively: count = 1 + countNodes(root.left) + countNodes(root.right)
5. Optimization
   • Since one subtree (left or right) will always be perfect, we can avoid traversing it and compute its size directly using (1 << h) - 1.

This gives an O(log² n) complexity because:

• Each height computation takes O(log n) (since tree height is log n for complete trees).
• We perform this height calculation at most O(log n) times due to recursion.

---

Step-by-Step Algorithm

1. If root == null, return 0.
2. Compute leftHeight = getLeftHeight(root).
3. Compute rightHeight = getRightHeight(root).
4. If leftHeight == rightHeight, return (1 << leftHeight) - 1.
5. Otherwise, recursively compute: return 1 + countNodes(root.left) + countNodes(root.right)

---

Java Code Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class CountCompleteTreeNodes {

    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        
        int leftHeight = getLeftHeight(root);
        int rightHeight = getRightHeight(root);
        
        // If heights are equal, it's a perfect binary tree
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) - 1;
        }
        
        // Otherwise, recursively count both subtrees
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    private int getLeftHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.left;
        }
        return height;
    }
    
    private int getRightHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.right;
        }
        return height;
    }
}

---

Complexity Analysis

• Time Complexity: O(log² n)
  Each recursive step computes the height of left and right subtrees, taking O(log n) each, and we do this for O(log n) recursive levels.
• Space Complexity: O(log n)
  Due to recursive stack space proportional to the height of the tree.

---

Alternative Approach (Iterative BFS)

A simple iterative BFS traversal using a queue would also give the total count:

int count = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    count++;
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
}
return count;

However, this takes O(n) time and does not leverage the complete tree structure.