Problem statement

You are given the root of a complete binary tree: every level is completely filled except possibly the last, and the nodes of the last level are packed as far left as possible.

Return the number of nodes in the tree. Aim for an algorithm that runs in less than O(n) time.

Example 1

Input: root = [1,2,3,4,5,6]
Output: 6
Explanation: Two full levels plus three nodes on the last one.

Example 2

Input: root = []
Output: 0
Explanation: The empty tree has no nodes.

Example 3

Input: root = [1]
Output: 1
Explanation: Just the root.

Constraints

• 0 <= number of nodes <= 5 * 10^4
• 0 <= Node.val <= 5 * 10^4
• the tree is complete

Hints for Count Complete Tree Nodes

1. Hint 1

   Counting every node is O(n). The completeness should let you skip whole subtrees.

2. Hint 2

   Walk down the leftmost path and the rightmost path. If they are equally long, the tree is perfect and has 2^h - 1 nodes.

3. Hint 3

   Otherwise count 1 + count(left) + count(right): at least one of the two subtrees is perfect and is answered by the height check at once.

How to solve Count Complete Tree Nodes

A perfect tree of height h has 2^h - 1 nodes, and checking whether a complete subtree is perfect costs only its height: compare the length of its leftmost path with the length of its rightmost path. Recursing only where the check fails touches O(log n) subtrees.

Approach

1. If the node is null, return 0.
2. Measure lh, the number of nodes on the path that always goes left, and rh, the number on the path that always goes right.
3. If lh == rh, the subtree is perfect: return 2^lh - 1.
4. Otherwise return 1 + countNodes(left) + countNodes(right).

Why it works

In a complete tree, the leftmost path reaches the deepest level. If the rightmost path is just as long, the last level is full, so the tree is perfect. If not, the last level's boundary lies in one subtree: the other subtree is perfect and stops after one height check, so each level of the recursion does real work in only one subtree.

Complexity

• Time — O(log² n) — O(log n) levels, each with O(log n) height walks
• Space — O(log n) for the recursion

Pitfalls

• Count heights in nodes, not edges, so a perfect tree of height h has 2^h - 1 nodes.
• A plain traversal is accepted for correctness but misses what the problem is about.

Reference solution

Python

from typing import Optional

def countNodes(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    lh, node = 0, root
    while node:
        lh += 1
        node = node.left
    rh, node = 0, root
    while node:
        rh += 1
        node = node.right
    if lh == rh:
        return (1 << lh) - 1
    return 1 + countNodes(root.left) + countNodes(root.right)

Java

public static int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = 0, rh = 0;
    for (TreeNode node = root; node != null; node = node.left) lh++;
    for (TreeNode node = root; node != null; node = node.right) rh++;
    if (lh == rh) return (1 << lh) - 1;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

C++

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int lh = 0, rh = 0;
    for (TreeNode* node = root; node; node = node->left) lh++;
    for (TreeNode* node = root; node; node = node->right) rh++;
    if (lh == rh) return (1 << lh) - 1;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

JavaScript

var countNodes = function(root) {
    if (root === null) return 0;
    var lh = 0, rh = 0, node;
    for (node = root; node !== null; node = node.left) lh++;
    for (node = root; node !== null; node = node.right) rh++;
    if (lh === rh) return (1 << lh) - 1;
    return 1 + countNodes(root.left) + countNodes(root.right);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More binary search problems

• Count BST Nodes That Lie in a Given Range Easy
• Ceil in BST Easy
• Range Sum of BST Easy
• Search in a Binary Search Tree Easy
• Find Nth Root of M Easy
• Find Target Indices After Sorting Array Easy