177. Count Complete Tree Nodes

For a complete tree, walk the leftmost and rightmost spines. If their heights are equal, the tree is perfectly filled and has exactly 2^h - 1 nodes — computed instantly. Otherwise, recurse into both children; the completeness guarantees one side is always perfect, giving an O(log^2 n) algorithm.

Idea

A perfect binary tree of height h has exactly 2^h - 1 nodes. For a complete tree, measure the leftmost spine height and the rightmost spine height:

• If they're equal, the tree is perfect → return 2^h - 1 with no recursion.
• If not, the last level is partially filled; recurse into both subtrees and add 1. Completeness ensures at least one subtree is perfect, so each recursion does O(log n) work over O(log n) levels.

Algorithm

1. If root is null, return 0.
2. lh = height going only left; rh = height going only right.
3. If lh == rh, return (1 << lh) - 1.
4. Else return 1 + countNodes(left) + countNodes(right).

Worked example: [1,2,3,4,5,6]

Left spine height 3, right spine height 3? No — the last level isn't full, so recurse. The tree has 6 nodes.

Complexity

• Time: O(log² n) — better than the O(n) naive count.
• Space: O(log n).

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lh = height(root, true);
        int rh = height(root, false);
        if (lh == rh) {
            return (1 << lh) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    private int height(TreeNode node, boolean goLeft) {
        int h = 0;
        while (node != null) {
            h++;
            node = goLeft ? node.left : node.right;
        }
        return h;
    }
}