L32. Count Total Nodes in a Complete Binary Tree | $O(\log^2 N)$ Approach

Counting the total number of nodes in a complete binary tree is a classic Data Structures and Algorithms problem. While a naive traversal inspects every single node in $O(N)$ time, leveraging the structural properties of complete binary trees enables a highly optimized recursive approach running in $O(\log^2 N)$ time.

1. Problem Statement & Definition of a Complete Binary Tree

A Complete Binary Tree is a specialized binary tree with two strict structural guarantees:

1. Fully filled levels: Every single level, except possibly the last (deepest) level, is completely filled with nodes.
2. Left-aligned last level: All nodes in the final level are positioned as far left as possible.

Problem Objective: Given the root of a complete binary tree, design an algorithm to compute and return the total number of nodes in time complexity strictly faster than $O(N)$.

2. The Naive Approach: Tree Traversals ($O(N)$ Time)

The most intuitive way to count nodes is to visit every single node in the tree using any standard traversal strategy (In-order, Pre-order, Post-order, or Level-order/BFS).

How It Works:

• Initialize a running counter = 0.
• Traverse the tree node by node.
• Increment counter++ upon visiting each node.

Complexity Analysis:

• Time Complexity: $\mathcal{O}(N)$, because the algorithm must visit all $N$ nodes in the tree.
• Auxiliary Space Complexity: $\mathcal{O}(H)$, where $H$ is the height of the tree. For a general binary tree, this can be $\mathcal{O}(N)$ in the worst case (skewed tree). However, for a complete binary tree, the maximum height is bounded by $\log_2 N$, resulting in an auxiliary stack space of $\mathcal{O}(\log N)$.

3. Core Mental Model: The Perfect Subtree Shortcut

To beat $\mathcal{O}(N)$, we must avoid traversing every subtree node-by-node. Instead, we can exploit a powerful mathematical property of Perfect Binary Trees.

Real-Life Analogy

Imagine auditing a massive box of identical books arranged in neat rows. If you know a particular section is completely full with every single row packed to capacity, you don't need to count every single book individually. You can simply calculate the total using geometry ($2^{\text{height}} - 1$). You only spend time counting books manually in the single partial, incomplete row at the bottom.

In a complete binary tree, any subtree whose left height equals its right height is guaranteed to be a perfect binary tree (all levels completely filled).

For a perfect binary tree of height $h$, the exact number of nodes is given by:

This means if we check a subtree and find that its left height equals its right height, we can immediately return its node count in $\mathcal{O}(1)$ time without visiting any of its internal nodes!

4. Step-by-Step Algorithm Design

When visiting any node during our recursive traversal, we perform the following steps:

1. Base Case: If the current node is null, return 0.
2. Compute Left Height: Traverse down the leftmost path from the current node to find the left height (leftHeight).
3. Compute Right Height: Traverse down the rightmost path from the current node to find the right height (rightHeight).
4. Height Comparison:
   • If leftHeight == rightHeight: The subtree rooted at this node is a perfect binary tree. Instantly calculate the node count using $2^{\text{height}} - 1$ and return it.
   • If leftHeight != rightHeight: The subtree is not perfect. We must account for the current node (1), recursively compute the nodes in the left subtree, recursively compute the nodes in the right subtree, and sum them up: 1 + countNodes(root->left) + countNodes(root->right).

5. Complete Flow Walkthrough

Let's trace how the algorithm evaluates a complete binary tree with 11 nodes:

               [Root: 1]
              /         \
          [2]             [3]
         /   \           /   \
       [4]   [5]       [6]   [7]
      /   \  /
    [8]   [9][10] [11]

1. At Root 1:

   • Compute leftHeight by going left-left-left... -> Height = 4.
   • Compute rightHeight by going right-right-right... -> Height = 3.
   • Since 4 != 3, this is not a perfect subtree.
   • Result will be: 1 + countNodes(left) + countNodes(right).

2. At Left Child 2:

   • Compute leftHeight -> Height = 3.
   • Compute rightHeight -> Height = 3.
   • Since 3 == 3, this is a perfect binary tree!
   • Instantly return $2^3 - 1 = 7$ nodes without inspecting nodes 4, 5, 8, 9, 10, 11.

3. At Right Child 3:

   • Compute leftHeight -> Height = 2.
   • Compute rightHeight -> Height = 2.
   • Since 2 == 2, this is a perfect binary tree!
   • Instantly return $2^2 - 1 = 3$ nodes without inspecting nodes 6, 7.

4. Final Combination at Root 1:

   • Total Nodes = 1 (root) + 7 (left subtree) + 3 (right subtree) = 11.

6. Implementation Code (C++ and Java)

Below are the complete, production-ready implementations in C++ and Java.

C++ Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int leftHeight = getLeftHeight(root);
        int rightHeight = getRightHeight(root);

        // If left and right heights are equal, it's a perfect binary tree
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) - 1; // Equivalent to (2^leftHeight - 1)
        }

        // Otherwise, recursively count nodes in left and right subtrees + current node
        return 1 + countNodes(root->left) + countNodes(root->right);
    }

private:
    int getLeftHeight(TreeNode* node) {
        int height = 0;
        while (node != nullptr) {
            height++;
            node = node->left;
        }
        return height;
    }

    int getRightHeight(TreeNode* node) {
        int height = 0;
        while (node != nullptr) {
            height++;
            node = node->right;
        }
        return height;
    }
};

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftHeight = getLeftHeight(root);
        int rightHeight = getRightHeight(root);

        // If left and right heights are equal, it's a complete / perfect subtree
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) - 1; // (2^leftHeight) - 1
        }

        // Recursive step: 1 (for root) + left count + right count
        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;
    }
}

7. Complexity Analysis of the Optimized Approach

8. Summary and Key Takeaways

• Definition Mastery: A complete binary tree has all levels filled except possibly the last, with nodes packed to the left.
• The Inefficiency of Brute Force: Standard traversals inspect every node, resulting in an $\mathcal{O}(N)$ time complexity.
• The Height Shortcut: If the left height and right height of any subtree match, that subtree is a perfect binary tree, and its node count can be computed instantly via $2^h - 1$.
• Logarithmic Height Checks: Finding the left and right height takes $\mathcal{O}(\log N)$ time by traversing single straight paths down the tree.
• Recursive Divide-and-Conquer: When heights do not match, the algorithm recurses down both children while adding $1$ for the current node.
• Superior Performance: By combining height checks with recursion, the time complexity drops dramatically from linear $\mathcal{O}(N)$ to sub-linear $\mathcal{O}(\log^2 N)$.
• Auxiliary Stack Efficiency: Due to the balanced nature of complete trees, recursion stack depth remains bounded at $\mathcal{O}(\log N)$.