Practice/Google/Leetcode 222. Count Complete Tree Nodes

Leetcode 222. Count Complete Tree Nodes

CodingMust

Problem

You are given the root of a complete binary tree. Your task is to calculate and return the total number of nodes in the tree.

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

• All levels are completely filled except possibly the last level
• The last level has all nodes as far left as possible

The challenge is to solve this problem more efficiently than O(n) time complexity by leveraging the properties of a complete binary tree. A naive solution would visit every node, but you can do better by taking advantage of the tree's structure.

Requirements

1. Count and return the total number of nodes in the complete binary tree
2. Exploit the complete tree property to achieve better than O(n) time complexity
3. Handle edge cases including empty trees and single-node trees
4. The solution should work for trees of any valid size

Constraints

• The number of nodes in the tree is in the range [0, 50000]
• 0 ≤= Node.val ≤= 50000
• The tree is guaranteed to be a complete binary tree
• Target time complexity: O(log²n) where n is the number of nodes
• Space complexity should be O(log n) for the recursion stack

Examples

Example 1:

Input: root = [1,2,3,4,5,6] 1 / \ 2 3 / \ / 4 5 6 Output: 6 Explanation: The tree has 6 nodes in total.

Example 2:

Input: root = [] Output: 0 Explanation: An empty tree has no nodes.

Example 3:

Input: root = [1] Output: 1 Explanation: A single node tree contains exactly one node.

Example 4:

Input: root = [1,2,3,4,5,6,7] 1 / \ 2 3 / \ / \ 4 5 6 7 Output: 7 Explanation: This is a perfect binary tree with all levels completely filled.