Count Complete Tree Nodes

EasyTrees · DFS · Binary Search on Height🧩 Tree DFS LeetCode #222 ↗Updated Oct 30, 2026

Problem

Given the root of a complete binary tree — every level is full except possibly the last, whose nodes are packed to the left — return how many nodes it has. Aim for better than O(n).

Input[1,2,3,4,5,6]Output6

Input[]Output0

Input[1]Output1

0 ≤ nodes ≤ 5·10⁴ · 0 ≤ Node.val ≤ 5·10⁴ · the tree is complete · Follow-up: beat O(n).

Try it yourself

Java

class Solution {
    public int countNodes(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

If the leftmost and rightmost spines have the same length h, the tree is perfect and has 2^h - 1 nodes — no need to visit them. In a complete tree, at least one child subtree is always perfect, so only one branch per level needs real work.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForcePlain DFS Count

Time O(n)Space O(log n)

Ignore completeness: a tree's size is 1 + size(left) + size(right), with an empty tree counting 0. Every node is visited once; the recursion depth is the height, which is O(log n) for a complete tree.

Java

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Always correct, but wastes the “complete” guarantee and misses the follow-up.

OptimalPerfect-Subtree Shortcut

Time O(log² n)Space O(log n)

Measure the left spine and right spine (O(log n) each). Equal ⇒ perfect, return 2^h - 1 at once. Otherwise recurse into both children: one of them is perfect and returns after its spine check, so only one O(log n) path goes deeper — O(log n) levels × O(log n) work.

Java

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = 0, rh = 0;
    for (TreeNode n = root; n != null; n = n.left) lh++;
    for (TreeNode n = root; n != null; n = n.right) rh++;
    if (lh == rh) return (1 << lh) - 1; // perfect tree: 2^h - 1 nodes
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Exploits completeness to skip whole perfect subtrees — answers the follow-up.

Pro tip

Alternative with the same bound: binary-search which last-level slot is filled, walking root-to-leaf by the index bits for each probe.

At a glance

Level	Approach	Time	Space
Brute Force	Plain DFS Count	`O(n)`	`O(log n)`
Optimal	Perfect-Subtree Shortcut	`O(log² n)`	`O(log n)`

Common pitfalls

Writing 2 ^ h in Java — that's XOR; use 1 << h.
Comparing height(left) with height(right) via full DFS — back to O(n).
Measuring only the left spine — it can't tell a perfect tree from a partially filled one.

Interview tips

Give the O(n) count first, then ask yourself what “complete” buys you.
Argue the O(log² n) bound: at most one non-perfect child per level.
Mention the last-level binary search as an equivalent alternative.

Pattern

Structural shortcut on complete/perfect trees → when the shape is guaranteed, compute sizes from heights instead of visiting nodes.

My notes saved in this browser