Count Complete Tree Nodes

Problem

Given a complete binary tree, count nodes in O(log^2 n) time (not O(n)).

Key insight: Compare leftmost and rightmost depths. If equal → perfect binary tree with 2^h - 1 nodes. Otherwise recurse on subtrees.

Solutions

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

// Java
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = 0, rh = 0;
    TreeNode l = root, r = root;
    while (l != null) { lh++; l = l.left; }
    while (r != null) { rh++; r = r.right; }
    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;
    let l = root, r = root;
    while (l) { lh++; l = l.left; }
    while (r) { rh++; r = r.right; }
    if (lh === rh) return (1 << lh) - 1;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

# Python
def countNodes(root):
    if not root:
        return 0
    lh = rh = 0
    l = r = 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)

Complexity

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

Key Insight

A complete binary tree has a perfect subtree when left-height == right-height. Skip counting those subtrees entirely.