Count Complete Tree Nodes

Problem

You are given the root of a complete binary tree: every level is fully filled except possibly the last, and the last level’s nodes are packed as far left as possible. Return the total number of nodes.

Counting by visiting every node is easy — the real task is to exploit completeness and do it in less than O(n) time.

Examples

Example 1

Input:  root = [1, 2, 3, 4, 5, 6]

            1
          /   \
         2     3
        / \   /
       4   5 6

Output: 6

Two full levels (3 nodes) plus 3 left-packed nodes on the last level.

Example 2

Input:  root = []
Output: 0

Empty tree, zero nodes.

Example 3

Input:  root = [1, 2, 3, 4, 5, 6, 7]
Output: 7

A perfect tree of height 3 has 2^3 - 1 = 7 nodes — no traversal needed once you know it’s perfect.

Constraints

• Number of nodes is in [0, 5 * 10^4].
• 0 <= Node.val <= 5 * 10^4
• The tree is guaranteed complete — this is the property your algorithm must exploit.
• Target complexity: better than O(n); the classic answers run in O(log^2 n).

Think about it first

TL;DR

Exploit completeness: compare left/right spine heights and resolve perfect subtrees by formula — O(log^2 n) time, O(log n) space.

Approach 1 — Brute force: count every node

Ignore completeness entirely: the size of a tree is 1 plus the sizes of its subtrees.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Complexity: O(n) time, O(log n) stack (a complete tree’s height is O(log n)). It passes at n <= 5 * 10^4, but it discards the completeness guarantee — the problem explicitly asks for sub-linear, so this is the answer to beat.

Approach 2 — Spine heights + perfect-tree formula (canonical)

The insight: a perfect tree of height h has exactly 2^h - 1 nodes, and its height is measurable in O(h) by walking one spine. In a complete tree, the left-only depth equals the right-only depth iff the tree is perfect. If they differ, recurse on the two children — and because both children are complete and at least one is perfect, one branch always terminates instantly by formula, so only one recursion chain survives.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def left_depth(node: Optional[TreeNode]) -> int:
            d = 0
            while node:
                d += 1
                node = node.left
            return d

        def right_depth(node: Optional[TreeNode]) -> int:
            d = 0
            while node:
                d += 1
                node = node.right
            return d

        if not root:
            return 0
        lh = left_depth(root)
        rh = right_depth(root)
        if lh == rh:                      # perfect subtree
            return (1 << lh) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Walkthrough on Example 1 ([1, 2, 3, 4, 5, 6]):

1. Root 1: left spine 1→2→4 gives lh = 3; right spine 1→3 (node 3 has no right child) gives rh = 2. Not perfect → recurse.
2. Subtree at 2: lh = 2 (2→4), rh = 2 (2→5) → perfect → 2^2 - 1 = 3.
3. Subtree at 3: lh = 2 (3→6), rh = 1 → recurse: subtree at 6 is perfect (2^1 - 1 = 1), right subtree empty (0) → 1 + 1 + 0 = 2.
4. Total: 1 + 3 + 2 = 6. Correct.

Complexity: O(log^2 n) time — the recursion descends O(log n) levels (one non-formula branch per level), each computing spine depths in O(log n); O(log n) recursion stack.

Approach 3 — Binary search for the last leaf

The insight: a complete tree is “a perfect tree of depth d plus a left-packed run of leaves on level d”. The upper levels contribute exactly 2^d - 1 nodes, so the only unknown is how many last-level leaves exist — and since they’re left-packed, existence is monotone (all present up to some index, all absent after). That’s a textbook binary search (the classical halving search over a monotone predicate). You can test whether leaf index i exists in O(d) by reading i’s bits as left/right turns from the root.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # depth in edges of the leftmost path
        d = 0
        node = root
        while node.left:
            d += 1
            node = node.left
        if d == 0:
            return 1

        def exists(idx: int) -> bool:
            """Does leaf number idx (0-based) exist on level d?"""
            lo, hi = 0, (1 << d) - 1
            node = root
            for _ in range(d):
                mid = (lo + hi) // 2
                if idx <= mid:
                    node = node.left
                    hi = mid
                else:
                    node = node.right
                    lo = mid + 1
            return node is not None

        # binary search the count of existing leaves in [1, 2^d]
        lo, hi = 1, (1 << d)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if exists(mid - 1):
                lo = mid
            else:
                hi = mid - 1
        return (1 << d) - 1 + lo

Walkthrough on Example 1: leftmost path 1→2→4 gives d = 2, so levels 0–1 hold 2^2 - 1 = 3 nodes and level 2 has capacity 4. Leaves present: indices 0, 1, 2 (nodes 4, 5, 6). The outer binary search probes exists(2) → navigate: range [0,3], idx 2 > mid 1 → go right to 3, range [2,3], idx 2 <= mid 2 → go left to 6 → exists → lo = 3; then exists(3) → path right,right → None → absent. Count = 3, answer 3 + 3 = 6.

Complexity: O(log^2 n) time — O(log n) binary-search probes, each an O(log n) root-to-leaf walk; O(1) extra space (iterative).

Common pitfalls

• Confusing height-in-nodes with height-in-edges — 2^h - 1 uses the node count of the spine; mixing conventions is the top source of off-by-one answers.
• In Approach 2, computing full subtree heights instead of spine depths — the whole speedup depends on the O(log n) spine walk.
• In Approach 3, binary-searching leaf indices with the wrong bias ((lo + hi) // 2 vs (lo + hi + 1) // 2) and looping forever, or forgetting the single-node case d == 0.
• Claiming Approach 2 is O(log n): each level re-measures spines, so it is genuinely O(log^2 n).

Pattern takeaway

When a tree problem hands you a structural guarantee (complete, perfect, balanced), the intended solution converts structure into arithmetic: a perfect subtree needs no traversal, just 2^h - 1. Learn to spot the decomposition “complete = perfect part + monotone fringe” — it turns counting into spine walks plus either a self-similar recursion or a binary search over the fringe, both O(log^2 n).