58. Count Complete Tree Nodes

A large-scale infrastructure system organizes data in the form of a complete binary tree, where:

• all levels are completely filled except possibly the last
• the last level is filled from left to right

Such structures are commonly used in:

• heap implementations
• priority queues
• indexing systems

The system frequently needs to count the total number of nodes. A naive traversal would take O(n) time, but due to the special structure of a complete binary tree, the system expects a more optimized solution.

Your task is to leverage the properties of a complete binary tree to compute the number of nodes efficiently.

This is a common interview problem asked in Google, Amazon, Microsoft, Meta, and other top companies.

Your Task

Given the root of a complete binary tree, return the total number of nodes in the tree.

Input Format

• root: root node of a complete binary tree

Each node:

TreeNode { int val; TreeNode left; TreeNode right;}

Output Format

• Integer representing total number of nodes

Examples

Constraints

• 0 ≤ number of nodes ≤ 100,000
• 0 ≤ Node.val ≤ 100,000
• Tree is complete