Count Complete Tree Nodes

Problem Statement

This task involves formulating an algorithm to determine the number of nodes in a complete binary tree, given its root. In a complete binary tree, every level is fully populated except for potentially the last level, which must have all its nodes aligned to the left. The algorithm should efficiently compute the total node count, striving to achieve a time complexity lower than O(n), where n represents the total number of nodes.

Examples

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

Constraints

• The number of nodes in the tree is in the range [0, 5 * 104].
• 0 <= Node.val <= 5 * 104
• The tree is guaranteed to be complete.

Approach and Intuition

The problem at hand is to count the nodes in a complete binary tree in less than linear time. Given the structured nature of a complete binary tree, straightforward traversal methods like breadth-first or depth-first (which inherently have O(n) complexity) are not optimal. Here's a strategic approach to solve this efficiently:

Example Illustrations

• Example 1:

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

  Output: 6

  This input describes a complete binary tree with three levels. All the levels are fully filled, hence a direct count gives six nodes.

• Example 2:

  Input: root = []

  Output: 0

  This represents an empty tree. Consequently, the number of nodes is zero.

• Example 3:

  Input: root = [1]

  Output: 1

  This is a tree with just one node, which forms the root and thus there is only one node.

Intuitive Steps

1. Check if the tree is empty, which directly yields a count of zero.
2. Utilize the properties of the complete binary tree to determine tree height quickly by traversing left-child pointers until reaching a null.
3. For counting the nodes especially in the last level:
   • Apply binary search on the last level to determine how many nodes it contains. Convert potential node positions to their equivalent paths and verify these paths exist in the tree.
4. Sum the nodes from all completely filled levels (which is straightforward to calculate using the height) with the node count obtained from the last level.

This approach efficiently narrows down the search space and leverages the structured nature of complete binary trees, which avoids unnecessary processing of each node.

Constraints Implications

• Since node values and array size are significantly large, optimizations beyond basic traversal are necessary to achieve sub-linear performance.
• The constraint that tree architecture must be complete simplifies certain assumptions and focuses efforts on counting terminal nodes smartly using binary search methodologies within the last level.

Solutions

class Solution {
    // Calculate depth of tree
    public int findDepth(TreeNode node) {
        int depth = 0;
        while (node.left != null) {
            node = node.left;
            depth++;
        }
        return depth;
    }
    
    // Verify if node at index exists
    public boolean checkExistence(int index, int depth, TreeNode node) {
        int low = 0, high = (int)Math.pow(2, depth) - 1;
        int mid;
        for (int level = 0; level < depth; level++) {
            mid = low + (high - low) / 2;
            if (index <= mid) {
                node = node.left;
                high = mid;
            } else {
                node = node.right;
                low = mid + 1;
            }
        }
        return node != null;
    }
    
    public int countNodes(TreeNode rootNode) {
        if (rootNode == null) return 0;
    
        int treeDepth = findDepth(rootNode);
        if (treeDepth == 0) return 1;
    
        int leftBound = 1, rightBound = (int)Math.pow(2, treeDepth) - 1;
        int median;
        while (leftBound <= rightBound) {
            median = leftBound + (rightBound - leftBound) / 2;
            if (checkExistence(median, treeDepth, rootNode)) leftBound = median + 1;
            else rightBound = median - 1;
        }
    
        // Return total nodes calculated
        return (int)Math.pow(2, treeDepth) - 1 + leftBound;
    }
}