Count Complete Tree Nodes — InterviewPrepKit

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.

Visiting every node is straightforward. The task is to exploit completeness and count 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

Hint 1

If the tree were *perfect* (every level full), how many nodes would it have as a function of its height — and how cheaply can you measure the height?

Hint 2

In a complete tree, walk left-only and right-only from the root. If those two depths are equal, the tree is perfect and you're done with a formula. If not, what do you know about the left and right subtrees?

Hint 3

Both subtrees of any node in a complete tree are themselves complete, and at least one of them is perfect. Recurse: at each node, compare left-spine and right-spine heights; one side resolves by formula, the other by recursion — only O(log n) recursive steps, each doing an O(log n) height walk. Alternatively, binary-search for the last existing leaf using bit-path navigation.

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


def countNodes(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return 1 + countNodes(root.left) + 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 ignores the completeness guarantee. The problem asks for sub-linear time, so the approaches below improve on this.

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

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. Because both children are complete and at least one is perfect, one branch terminates immediately by formula, so only one branch recurses further at each level.

# 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


def countNodes(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 + countNodes(root.left) + countNodes(root.right)

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

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.
Subtree at 2: lh = 2 (2→4), rh = 2 (2→5) → perfect → 2^2 - 1 = 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.
Total: 1 + 3 + 2 = 6. Correct.

flowchart TD
    N1["1 (lh=3, rh=2: recurse)"]
    N2["2 (lh=rh=2: perfect, +3)"]
    N3["3 (lh=2, rh=1: recurse)"]
    N4["4"]
    N5["5"]
    N6["6 (perfect, +1)"]
    N1 --> N2
    N1 --> N3
    N2 --> N4
    N2 --> N5
    N3 --> N6

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

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. Because they are left-packed, existence is monotone: all present up to some index, all absent after. That monotone predicate supports a binary search. 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


def countNodes(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 gives a structural guarantee (complete, perfect, balanced), the intended solution converts structure into arithmetic: a perfect subtree needs no traversal, just 2^h - 1. The decomposition “complete = perfect part + monotone fringe” turns counting into spine walks plus either a self-similar recursion or a binary search over the fringe, both O(log^2 n).