Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count Complete Tree Nodes

EASYProblemSolveExternal Links

Description

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

A complete binary tree is a binary tree where every level is fully filled with nodes, except possibly the very last level. On that last level, all nodes are packed as far left as possible. If the tree has height h, the last level can hold between 1 and 2^h nodes.

Your algorithm should run in less than O(n) time complexity, where n is the number of nodes. In other words, you should take advantage of the complete tree structure rather than visiting every node.

Examples

Example 1

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

        1
       / \
      2   3
     / \ /
    4  5 6

Output: 6

Explanation: The tree has 3 levels. Levels 0 and 1 are fully filled (nodes 1, 2, 3). Level 2 has 3 out of a possible 4 nodes (nodes 4, 5, 6 packed from the left). Total: 6 nodes.

Example 2

Input: root = []

Output: 0

Explanation: An empty tree has no nodes.

Example 3

Input: root = [1]

Output: 1

Explanation: The tree contains only the root node.

Constraints

  • The number of nodes in the tree is in the range [0, 5 × 10^4].
  • 0 <= Node.val <= 5 × 10^4
  • The tree is guaranteed to be complete.

Editorial

Brute Force - Recursive Traversal

Intuition

The most straightforward way to count nodes in any binary tree is to visit every single one. At each node, the count equals 1 (the node itself) plus the total nodes in its left subtree plus the total nodes in its right subtree. When we reach a null pointer (beyond a leaf), we return 0.

This recursive pattern is clean and simple. Think of it like counting people in a building: you go to every room, count the person there, and add up all the rooms. It works perfectly, but you have to physically visit every room.

For this problem, the approach correctly counts all nodes. However, it completely ignores the fact that the tree is complete. It treats the input as if it were an arbitrary binary tree, spending O(n) time even though the rigid structure of a complete tree offers shortcuts.

Step-by-Step Explanation

Let's trace through Example 1 with root = [1, 2, 3, 4, 5, 6]:

        1
       / \
      2   3
     / \ /
    4  5 6

Step 1: Start at root node 1. We need count(left) and count(right) before we can compute root's total. Recurse into the left subtree first.

Step 2: At node 2. count(2) = 1 + count(left) + count(right). Recurse into left child: node 4.

Step 3: At node 4. Both children are null. count(null) = 0 for each. count(4) = 1 + 0 + 0 = 1. Node 4 is a leaf.

Step 4: Back at node 2, visit right child: node 5. Both children are null. count(5) = 1 + 0 + 0 = 1. Another leaf.

Step 5: Now node 2 has both subtree counts. count(2) = 1 + count(4) + count(5) = 1 + 1 + 1 = 3. The left subtree of root contains 3 nodes.

Step 6: Back at root, recurse into right child: node 3. Its left child is node 6 (a leaf, count = 1). Its right child is null (count = 0).

Step 7: count(3) = 1 + 1 + 0 = 2. The right subtree of root contains 2 nodes.

Step 8: Root: count(1) = 1 + 3 + 2 = 6. We visited all 6 nodes to get this answer — every single node required its own function call.

Brute Force — Visiting Every Node — Watch how the recursive count visits every single node in the tree, computing subtree sizes bottom-up from leaves to root.

Algorithm

  1. If the current node is null, return 0.
  2. Recursively count nodes in the left subtree: leftCount = countNodes(root.left).
  3. Recursively count nodes in the right subtree: rightCount = countNodes(root.right).
  4. Return 1 + leftCount + rightCount.

Code

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        return 1 + countNodes(root->left) + countNodes(root->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)
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every single node in the tree exactly once. Each visit does O(1) work (addition). Total: O(n).

Space Complexity: O(h) where h = height of the tree

The recursive call stack goes as deep as the tree height. For a complete binary tree, h = O(log n). In the worst edge case of a single-branch tree (not complete but theoretically), it could be O(n). For guaranteed complete trees: O(log n).

Why This Approach Is Not Efficient

The brute force visits every single node, running in O(n) time. The problem explicitly asks for an algorithm faster than O(n). We're completely ignoring the most powerful constraint: the tree is complete.

A complete binary tree has a very rigid structure — every level except possibly the last is fully filled, and the last level is packed from the left. This means large portions of the tree are guaranteed to be perfect binary trees (every level fully filled).

Here's the key insight: for a perfect binary tree of height h, the number of nodes is exactly 2^h - 1. You can verify whether a subtree is perfect by simply comparing two path lengths:

  • The leftmost path (always going left from the root)
  • The rightmost path (always going right from the root)

If these two paths have the same length, the subtree must be perfect — and you know the node count without visiting any of its interior nodes.

For a complete tree with n nodes, the "boundary" where the last level ends lies along at most O(log n) subtrees. Each boundary check costs O(log n) to measure the heights. This yields O(log² n) total work — exponentially faster than O(n). For n = 50,000, that's roughly 250 operations instead of 50,000.

Bar chart comparing O(n) brute force with 50,000 operations vs O(log² n) optimal with approximately 250 operations
Bar chart comparing O(n) brute force with 50,000 operations vs O(log² n) optimal with approximately 250 operations

Optimal Approach - Exploit Complete Tree Property

Intuition

The trick is to detect when a subtree is a perfect binary tree and skip counting its nodes individually.

Here's how we detect perfection: from any node, measure the left height (follow left children all the way down) and the right height (follow right children all the way down). In a complete binary tree:

  • If left height equals right height, the subtree is perfect — every level is fully filled. The node count is exactly 2^h - 1 where h is the height. We're done instantly.
  • If left height is greater than right height, the subtree is not perfect — the last level boundary lies somewhere inside it. We recurse on both children to narrow down where the boundary is.

Why does this work? In a complete binary tree, the leftmost path is always the longest (or tied for longest), and the rightmost path is always the shortest (or tied). If they match, there's no "gap" in the last level — the subtree is fully filled.

Think of it like measuring a bookshelf. If the left edge and right edge are the same height, the shelf is completely full. You don't need to count every book — you know the capacity formula. If the edges differ, some books are missing from the right end, so you need to look more carefully.

Crucially, at each level of recursion, at least one of the two subtrees (left or right) will be detected as perfect and resolved in O(log n) time. This means the recursion only goes O(log n) levels deep, and each level costs O(log n) for height measurement. Total: O(log² n).

Step-by-Step Explanation

Let's trace Example 1 with root = [1, 2, 3, 4, 5, 6]:

        1
       / \
      2   3
     / \ /
    4  5 6

Step 1: At root node 1. Compute left height: follow left children 1→2→4→null = 3 levels. Compute right height: follow right children 1→3→null = 2 levels (node 3 has no right child).

Step 2: Left height (3) ≠ right height (2). The tree is NOT a perfect binary tree — the last level is only partially filled. We must recurse: count = 1 + countNodes(left) + countNodes(right).

Step 3: Recurse into left subtree (node 2). Left height: 2→4→null = 2 levels. Right height: 2→5→null = 2 levels.

Step 4: Left height (2) == right height (2). Node 2's subtree is a PERFECT binary tree! Count = 2^2 - 1 = 3. We know there are exactly 3 nodes (2, 4, 5) without visiting nodes 4 and 5 individually. Return 3.

Step 5: Recurse into right subtree (node 3). Left height: 3→6→null = 2 levels. Right height: 3→null = 1 level.

Step 6: Left height (2) ≠ right height (1). Not a perfect subtree. Node 3 has a left child but no right child. Recurse: count(3) = 1 + countNodes(6) + countNodes(null).

Step 7: At node 6: left height = 1, right height = 1. Equal → perfect single-node tree. Count = 2^1 - 1 = 1. Node 3's right child is null → returns 0.

Step 8: Node 3: 1 + 1 + 0 = 2. Root: 1 + 3 + 2 = 6. We found the answer by examining only 4 key decision points (nodes 1, 2, 3, 6) instead of visiting all 6 nodes. For larger trees, the savings grow dramatically.

Optimal — Detecting Perfect Subtrees and Skipping — Watch how the algorithm measures left and right heights to detect perfect subtrees, computing their size with a formula instead of visiting every node.

Algorithm

  1. If the root is null, return 0.
  2. Compute the left height: starting from root, follow left children and count the levels.
  3. Compute the right height: starting from root, follow right children and count the levels.
  4. If left height == right height:
    • The tree is a perfect binary tree. Return 2^height - 1.
  5. Otherwise:
    • The tree is complete but not perfect. Return 1 + countNodes(root.left) + countNodes(root.right).

Code

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;

        int leftHeight = getLeftHeight(root);
        int rightHeight = getRightHeight(root);

        if (leftHeight == rightHeight) {
            // Perfect binary tree: 2^h - 1 nodes
            return (1 << leftHeight) - 1;
        }

        // Not perfect: recurse on both subtrees
        return 1 + countNodes(root->left) + countNodes(root->right);
    }

private:
    int getLeftHeight(TreeNode* node) {
        int height = 0;
        while (node) {
            height++;
            node = node->left;
        }
        return height;
    }

    int getRightHeight(TreeNode* node) {
        int height = 0;
        while (node) {
            height++;
            node = node->right;
        }
        return height;
    }
};
from typing import Optional

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

        left_height = self._get_left_height(root)
        right_height = self._get_right_height(root)

        if left_height == right_height:
            # Perfect binary tree: 2^h - 1 nodes
            return (2 ** left_height) - 1

        # Not perfect: recurse on both subtrees
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def _get_left_height(self, node: Optional[TreeNode]) -> int:
        height = 0
        while node:
            height += 1
            node = node.left
        return height

    def _get_right_height(self, node: Optional[TreeNode]) -> int:
        height = 0
        while node:
            height += 1
            node = node.right
        return height
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        int leftHeight = getLeftHeight(root);
        int rightHeight = getRightHeight(root);

        if (leftHeight == rightHeight) {
            // Perfect binary tree: 2^h - 1 nodes
            return (1 << leftHeight) - 1;
        }

        // Not perfect: recurse on both subtrees
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    private int getLeftHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.left;
        }
        return height;
    }

    private int getRightHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.right;
        }
        return height;
    }
}

Complexity Analysis

Time Complexity: O(log² n)

At each level of recursion, we compute two heights in O(log n) time (just following one path down). The recursion depth is at most O(log n) because at each step, at least one subtree is detected as perfect and doesn't recurse further — only the subtree containing the "boundary" of the last level continues recursing. Total: O(log n) levels × O(log n) per level = O(log² n).

Space Complexity: O(log n)

The recursion depth is bounded by the height of the tree, which is O(log n) for a complete binary tree. Each stack frame uses O(1) space. The height computation uses O(1) extra space (just a counter and a pointer). Total: O(log n).