Count total nodes in a complete BT

Easy TUF ID 117 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a complete binary tree. Return the number of nodes in it.

A binary tree is complete when every level is completely filled except possibly the last one, and the nodes on the last level are packed as far to the left as possible. There are no gaps: if you number the slots of the tree level by level, left to right, the occupied slots are exactly 1, 2, ..., n.

Constraints (LeetCode version): up to 5 × 10^4 nodes, and the tree is guaranteed to be complete. Counting every node is easy; the interesting part is doing it in less than O(n) time by exploiting completeness.

Example 1

        1
      /   \
     2     3
    / \   /
   4   5 6
answer = 6      // the top two levels are full (3 nodes); the bottom level uses 3 of its 4 slots

Example 2

root = []       // empty tree
answer = 0

Example 3

root = [1]
answer = 1      // a single node is a complete (and perfect) tree

Approach 1: Brute force

Intuition. The number of nodes in any tree is one (the root) plus the count of the left subtree plus the count of the right subtree. A plain recursive traversal therefore answers the question for every binary tree, complete or not. It simply never uses the extra structure we were promised, so it must touch all n nodes.

Algorithm.

If the node is null, return 0.
Otherwise return 1 + count(left) + count(right).

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

Complexity. Time O(n): each node is visited once. Space O(log n) for the recursion stack, because a complete tree with n nodes has height floor(log2 n) + 1.

This is perfectly acceptable for 5 × 10^4 nodes, and in an interview it is a fine first answer. The follow-up is always: “the tree is complete, can you avoid visiting every node?”

Approach 2: Optimal, skip perfect subtrees

Intuition. A perfect binary tree (every level full) of height h has exactly 2^h - 1 nodes, so it can be counted without looking inside it. How do we recognise a perfect subtree cheaply? In a complete tree, walk down the leftmost path and count its length lh; walk down the rightmost path and count rh. The leftmost path always reaches the deepest level. If the rightmost path reaches the same depth, the last level is full all the way to the right, so the subtree is perfect and holds 2^lh - 1 nodes. If not, recurse: 1 + count(left) + count(right).

The reason this is fast: when a subtree is not perfect, at least one of its two children is perfect. Picture where the last level ends:

If it ends inside the right half, the left child’s subtree has its bottom level completely filled, so the left child is perfect.
If it ends inside the left half (or exactly at its end), the right child’s subtree has no nodes on the last level at all, so the right child is perfect, one level shorter.

Every subtree of a complete tree is itself complete, so the same argument applies all the way down. Of the two recursive calls, one returns immediately after its two height walks, and only the other one keeps descending. The recursion follows a single root-to-leaf path.

Algorithm.

If the node is null, return 0.
Compute lh by following left pointers and rh by following right pointers (both count the node itself).
If lh == rh, return (1 << lh) - 1.
Otherwise return 1 + count(left) + count(right).

static int optimal(TreeNode root) {
    if (root == null) return 0;
    int lh = leftHeight(root), rh = rightHeight(root);
    if (lh == rh) return (1 << lh) - 1;              // perfect subtree: 2^h - 1 nodes, no need to look inside
    return 1 + optimal(root.left) + optimal(root.right);
}

static int leftHeight(TreeNode node) {
    int h = 0;
    while (node != null) {
        h++;
        node = node.left;
    }
    return h;
}

static int rightHeight(TreeNode node) {
    int h = 0;
    while (node != null) {
        h++;
        node = node.right;
    }
    return h;
}

Dry run on Example 1:

call on node	leftHeight	rightHeight	result
1	3 (1, 2, 4)	2 (1, 3)	`1 + count(2) + count(3)`
2	2 (2, 4)	2 (2, 5)	perfect: `2^2 - 1 = 3`
3	2 (3, 6)	1 (3)	`1 + count(6) + count(null)`
6	1	1	perfect: `1`
null			`0`

Total 1 + 3 + (1 + 1 + 0) = 6. Node 4 and node 5 were never visited as recursive calls; the subtree at 2 was counted by formula.

Complexity. Time O(log^2 n): the recursion descends O(log n) levels along one path, and at each level it spends O(log n) on the two height walks. Space O(log n) for the recursion stack.

Use 1 << lh rather than Math.pow(2, lh). The shift is exact integer arithmetic; Math.pow returns a double and needs a cast.

Approach 3: Optimal, binary search on the last level

Intuition. A different way to use completeness. Let d be the depth of the bottom level (root at depth 0), found by walking left from the root. All levels above it are full, which accounts for 2^d - 1 nodes. The bottom level has 2^d slots numbered 0 to 2^d - 1, and because the tree is complete, the occupied slots form a prefix: slot p exists for every p up to some last position, and none after it. “Does slot p exist?” is therefore a monotone yes/no question, which is exactly what binary search is for.

To test one slot, walk from the root and halve the slot range at each level: slot p lies in the left subtree when p is in the lower half of the current range, otherwise in the right subtree. After d steps we are standing on slot p, or on null if it is empty.

Algorithm.

If the root is null, return 0.
Compute d by walking left from root.left.
Binary search for the last existing slot lo in [0, 2^d - 1]. Slot 0 always exists, so start with lo = 0. Use an upper middle mid = lo + (hi - lo + 1) / 2, otherwise lo = mid could loop forever when hi = lo + 1.
Return (2^d - 1) + (lo + 1).

static int optimalBinarySearch(TreeNode root) {
    if (root == null) return 0;
    int d = 0;                                        // depth of the bottom level, root at depth 0
    for (TreeNode t = root.left; t != null; t = t.left) d++;
    int lo = 0, hi = (1 << d) - 1;                    // bottom-level positions; position 0 always exists
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;             // round up so that lo = mid always makes progress
        if (exists(root, d, mid)) lo = mid; else hi = mid - 1;
    }
    return (1 << d) - 1 + lo + 1;                     // every level above the bottom, plus positions 0..lo
}

// walks from the root to bottom-level position pos, halving the range [0, 2^d - 1] at every step
static boolean exists(TreeNode root, int d, int pos) {
    int lo = 0, hi = (1 << d) - 1;
    TreeNode node = root;
    for (int level = 0; level < d; level++) {
        int mid = lo + (hi - lo) / 2;
        if (pos <= mid) {
            node = node.left;
            hi = mid;
        } else {
            node = node.right;
            lo = mid + 1;
        }
    }
    return node != null;
}

Complexity. Time O(log^2 n): the binary search makes O(d) = O(log n) probes and each probe walks d levels. Space O(1), since nothing is recursive.

Both optimal methods have the same asymptotic cost. The height-comparison version is shorter and the one most people remember; the binary-search version is fully iterative and makes the “prefix of the bottom level” structure explicit.

Edge cases and pitfalls

Empty tree. All three methods return 0 before touching any pointer.
Single node. leftHeight = rightHeight = 1, so Approach 2 returns 2^1 - 1 = 1. In Approach 3, d = 0, the search range is just slot 0, and the answer is 0 + 1 = 1.
Comparing the wrong heights. The trick needs the length of the leftmost and rightmost paths, which costs O(log n). Calling a general maxDepth function on each child instead costs O(n) per call and destroys the speed-up.
Only valid for complete trees. On an arbitrary tree, equal leftmost and rightmost depths do not imply a perfect tree. For example, take a root with two children where the left child has a single right child: both outer paths have length 2, the formula says 3, but the tree has 4 nodes. The method relies on the guarantee, so do not reuse it blindly elsewhere.
Off-by-one in the level count. leftHeight counts nodes (a single node has height 1), so the perfect-tree count is 2^h - 1. In Approach 3, d counts edges (the root is depth 0), so the full levels above the bottom hold 2^d - 1 nodes. Mixing the two conventions is the classic bug.
Overflow. With at most 5 × 10^4 nodes the height is at most 16, so 1 << h is safe in an int. The tests also run a perfect tree with 17 levels (131071 nodes) and a complete tree with 100000 nodes.

Maximum Depth in BT computes the general height that this problem deliberately avoids.
Check for balanced binary tree is another problem where comparing subtree heights is the key step.
Level Order Traversal visits the tree level by level, the order in which a complete tree is filled.
Maximum Width of BT uses the same heap-style slot numbering (2i + 1, 2i + 2) as Approach 3.

Count total nodes in a complete BT

Problem

Approach 1: Brute force

Approach 2: Optimal, skip perfect subtrees

Approach 3: Optimal, binary search on the last level

Edge cases and pitfalls

Related problems