The O(n) Club: Count Complete Tree Nodes Like a Binary Sorcerer

The O(n) Club: Count Complete Tree Nodes Like a Binary Sorcerer

⚡ TL;DR

You could count each node in your complete binary tree like a sleep-deprived census worker, or you could spot that glorious symmetry and count entire layers at once. Math > carpal tunnel. Here’s what not to do:

// Java brute-force (enjoy O(n) time!)
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

🧠 How Devs Usually Mess This Up

The classic moves:

• Brute-force bonanza: Still checking every node? Your CPU’s already filing a complaint.
• Perfect vs. complete tree mix-up: A perfect tree is as full as your Slack notifications, but a complete one just tries its best on the last row.
• Lopsided depth drama: Forgetting to carefully compare left and right edges makes your “math hack” a logic bug factory.
• Base case blind spots: Forget null checks, and watch your recursion go to infinite sadness.

🔍 What’s Actually Going On

This isn’t just counting—it’s sneaky accounting. In a complete binary tree, if the leftmost and rightmost path from root both have depth d, the tree’s perfect: just do 2^d – 1 and call it a day (or impress your interviewer early and hit the cafe). If not, some nodes are missing on the last row. In those cases, split the tree and count only where things got weird—recursively. You only do “real work” when you can’t shortcut with math.

🛠️ PseudoCode

• If the tree is null:
  return 0;
  Congrats, you found nothing.
• Walk left and right to get depths:
  int leftDepth = 0, rightDepth = 0; TreeNode l = root, r = root; while (l != null) { leftDepth++; l = l.left; } while (r != null) { rightDepth++; r = r.right; }
  This is your depth tape measure. Left and right only.
• If depths match:
  return (1 << leftDepth) - 1;
  You’re done! This subtree is perfect, you lucky dev!
• If not:
  return 1 + countNodes(root.left) + countNodes(root.right);
  Count root plus the wonky children. Recursion: it’s not just for stack overflows anymore!

💻 The Code

// Java, fancy version
definition for TreeNode supplied by LeetCode:
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int left = 0, right = 0;
    TreeNode l = root, r = root;
    while (l != null) {
        left++;
        l = l.left;
    }
    while (r != null) {
        right++;
        r = r.right;
    }
    if (left == right) {
        return (1 << left) - 1;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Single-node sadness: A tree with just one lonely node? Returns 1. (Still better than O(n).)
• Bitshift arrogance: (1 << left) - 1 is cool until left is zero. But hey, you checked for null, right?
• Complexity: It’s O((log n)^2) — the recursion rarely goes deep, but each time you measure depths it costs log n. Still, that’s mile-high performance compared to naive solutions.

🧠 Interviewer Brain-Tattoo

“When a tree’s perfectly balanced, do less. When it’s not, recurse—just not blindly.”