Number of Nodes in a Complete Binary Tree (Optimized)

Problem

Same as #46 but emphasizing the O(log^2 n) solution and its proof.

Key Insight

For each subproblem: compute left-height (go left), right-height (go right).

If equal: left subtree is perfect → size = 2^lh - 1 + 1 + right subtree
If unequal: right subtree is perfect (one level shorter) → size = left subtree + 1 + 2^rh - 1

# Python — recursive with perfect subtree shortcut
def countNodes(root):
    if not root:
        return 0
    lh = rh = 0
    l, r = root, root
    while l: lh += 1; l = l.left
    while r: rh += 1; r = r.right
    if lh == rh:
        return (1 << lh) - 1
    return 1 + countNodes(root.left) + countNodes(root.right)

// C++
int countNodes(TreeNode* root) {
    if (!root) return 0;
    int lh=0,rh=0;
    for(auto n=root;n;n=n->left)lh++;
    for(auto n=root;n;n=n->right)rh++;
    if(lh==rh)return(1<<lh)-1;
    return 1+countNodes(root->left)+countNodes(root->right);
}

// Java
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh=0,rh=0;
    for(TreeNode n=root;n!=null;n=n.left)lh++;
    for(TreeNode n=root;n!=null;n=n.right)rh++;
    if(lh==rh)return(1<<lh)-1;
    return 1+countNodes(root.left)+countNodes(root.right);
}

// JavaScript
function countNodes(root) {
    if (!root) return 0;
    let lh=0,rh=0;
    for(let n=root;n;n=n.left)lh++;
    for(let n=root;n;n=n.right)rh++;
    if(lh===rh)return(1<<lh)-1;
    return 1+countNodes(root.left)+countNodes(root.right);
}

Complexity

Time: O(log^2 n) — O(log n) levels, each O(log n) height check