Count Complete Tree Nodes (Optimized)

To solve this efficiently for Microsoft's standards, I first need to distinguish between a general binary tree and a complete one. A naive DFS or BFS would visit every node, taking O(N) time, which violates the requirement. Since we are given a complete binary tree, I can exploit its structural property: levels are filled left-to-right. My strategy involves comparing the height of the leftmost path versus the rightmost path. I will traverse down the left children to find the maximum depth, and similarly for the right children. Both operations take O(log N) time since the height of a balanced tree is logarithmic. If these two heights are equal, the tree is a perfect binary tree. In this case, I don't need to visit any nodes; I can directly calculate the total count using the formula 2^height minus 1. This gives me an O(1) solution for this branch. If the heights differ, it means the last level is not full. However, because it is complete, the left subtree must be a perfect binary tree of height h-1. The right subtree might be incomplete. I recursively apply the same logic to the right child while adding the size of the known perfect left subtree (2^(h-1) - 1) plus the root node. By repeating this, the recurrence relation becomes T(n) = T(n/2) + O(log n), which solves to O(log² n). This approach minimizes node visits significantly compared to standard traversal.