222. Count Complete Tree Nodes

EasyBit ManipulationTreeBinary SearchBinary Tree

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given the root of a complete binary tree and need to count the total number of nodes in the tree.

A complete binary tree has special properties:

Every level is completely filled with nodes, except possibly the last level
The last level fills nodes from left to right (all nodes are as far left as possible)
If the tree has height h, the last level can contain between 1 and 2^h nodes

The key constraint is that your algorithm must run in less than O(n) time complexity, where n is the number of nodes. This means you cannot simply visit every node to count them.

The solution leverages the complete-tree property. For any subtree, compare the height found by walking left edges with the height found by walking right edges. If those heights are equal, the subtree is perfect and its node count is 2^height - 1, so we do not need to visit every node in it.

If the heights differ, the subtree is not perfect, so we recursively count its left and right children. This avoids traversing full subtrees node by node and satisfies the required better-than-O(n) complexity.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Tree DFS?

This problem maps to Tree DFS through a short path in the full flowchart.

Recursively count nodes; when the left and right depths match the subtree is full and contributes 2^h - 1 directly without further recursion.

Open in Flowchart

Intuition

When counting nodes in a complete binary tree, the straightforward approach would be to visit every node. However, complete trees have enough structure for us to skip large perfect subtrees.

At each subtree, compute two heights:

left_height: follow left pointers until reaching None
right_height: follow right pointers until reaching None

If the two heights match, the subtree is a perfect binary tree. A perfect tree with height h contains (2^h) - 1 nodes, so we can return that value immediately.

If the heights differ, the subtree is complete but not perfect, so at least one child subtree may still be perfect. We recursively apply the same logic to the left and right children and add 1 for the current root.

Solution Approach

The solution uses recursive DFS with a perfect-subtree shortcut.

Base Case: When we encounter a None node (empty subtree), we return 0 since there are no nodes to count.

if root is None:
    return 0

Perfect Subtree Check: For any non-null node, calculate the leftmost and rightmost heights.

left_height = self.get_left_height(root)
right_height = self.get_right_height(root)
if left_height == right_height:
    return (1 << left_height) - 1

If these heights match, the subtree is perfect, and we can compute the answer directly.

Recursive Case: If the heights differ, recursively count the two children:

return 1 + self.countNodes(root.left) + self.countNodes(root.right)

The algorithm follows these steps:

Start at the root node
If the current node is None, return 0
Compute leftmost and rightmost heights from the current node
If the heights match, return (2^height) - 1
Otherwise, return 1 + countNodes(root.left) + countNodes(root.right)

Example walkthrough: For a perfect tree with 3 nodes, leftmost height and rightmost height are both 2, so the result is (2^2) - 1 = 3 without visiting the children separately.

Time Complexity: O(log^2 n) for a complete tree. At each level, height checks cost O(log n), and recursion descends through O(log n) levels.

Space Complexity: O(log n) for the recursion stack.

Example Walkthrough

Let's walk through counting nodes in a small complete binary tree with 6 nodes:

Step-by-step execution:

Start at root (1):
- Leftmost height is 3 (1 -> 2 -> 4)
- Rightmost height is 2 (1 -> 3)
- Heights differ, so the tree is not perfect. Return 1 + countNodes(2) + countNodes(3).
Process left subtree (node 2):
- Leftmost height is 2 (2 -> 4)
- Rightmost height is 2 (2 -> 5)
- Heights match, so this subtree is perfect and contains (2^2) - 1 = 3 nodes.
Process right subtree (node 3):
- Leftmost height is 2 (3 -> 6)
- Rightmost height is 1 (3)
- Heights differ, so return 1 + countNodes(6) + countNodes(None).
- Node 6 is perfect with height 1, so it contributes 1.
- None contributes 0.
- Node 3's subtree contributes 1 + 1 + 0 = 2.
Final calculation:
- Root's count: 1 + 3 + 2 = 6

The algorithm skips counting every node in the perfect left subtree individually, which is the key optimization for complete binary trees.

Solution Implementation

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8from typing import Optional
9
10class Solution:
11    def countNodes(self, root: Optional[TreeNode]) -> int:
12        if root is None:
13            return 0
14
15        left_height = self._left_height(root)
16        right_height = self._right_height(root)
17
18        if left_height == right_height:
19            return (1 << left_height) - 1
20
21        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
22
23    def _left_height(self, node: Optional[TreeNode]) -> int:
24        height = 0
25        while node:
26            height += 1
27            node = node.left
28        return height
29
30    def _right_height(self, node: Optional[TreeNode]) -> int:
31        height = 0
32        while node:
33            height += 1
34            node = node.right
35        return height
36

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public int countNodes(TreeNode root) {
18        if (root == null) {
19            return 0;
20        }
21
22        int leftHeight = getLeftHeight(root);
23        int rightHeight = getRightHeight(root);
24
25        if (leftHeight == rightHeight) {
26            return (1 << leftHeight) - 1;
27        }
28
29        return 1 + countNodes(root.left) + countNodes(root.right);
30    }
31
32    private int getLeftHeight(TreeNode node) {
33        int height = 0;
34        while (node != null) {
35            height++;
36            node = node.left;
37        }
38        return height;
39    }
40
41    private int getRightHeight(TreeNode node) {
42        int height = 0;
43        while (node != null) {
44            height++;
45            node = node.right;
46        }
47        return height;
48    }
49}
50

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int countNodes(TreeNode* root) {
15        if (!root) {
16            return 0;
17        }
18
19        int leftHeight = getLeftHeight(root);
20        int rightHeight = getRightHeight(root);
21
22        if (leftHeight == rightHeight) {
23            return (1 << leftHeight) - 1;
24        }
25
26        return 1 + countNodes(root->left) + countNodes(root->right);
27    }
28
29private:
30    int getLeftHeight(TreeNode* node) {
31        int height = 0;
32        while (node) {
33            height++;
34            node = node->left;
35        }
36        return height;
37    }
38
39    int getRightHeight(TreeNode* node) {
40        int height = 0;
41        while (node) {
42            height++;
43            node = node->right;
44        }
45        return height;
46    }
47};
48

1/**
2 * Definition for a binary tree node
3 */
4interface TreeNode {
5    val: number;
6    left: TreeNode | null;
7    right: TreeNode | null;
8}
9
10function countNodes(root: TreeNode | null): number {
11    if (!root) {
12        return 0;
13    }
14
15    const leftHeight = getLeftHeight(root);
16    const rightHeight = getRightHeight(root);
17
18    if (leftHeight === rightHeight) {
19        return (1 << leftHeight) - 1;
20    }
21
22    return 1 + countNodes(root.left) + countNodes(root.right);
23}
24
25function getLeftHeight(node: TreeNode | null): number {
26    let height = 0;
27    while (node) {
28        height++;
29        node = node.left;
30    }
31    return height;
32}
33
34function getRightHeight(node: TreeNode | null): number {
35    let height = 0;
36    while (node) {
37        height++;
38        node = node.right;
39    }
40    return height;
41}
42

Time and Space Complexity

Time Complexity: O(log^2 n), where n is the number of nodes in the complete binary tree.

At each recursive level, we compute the leftmost and rightmost heights, which costs O(log n) in a complete tree. The recursion descends through at most O(log n) levels because perfect subtrees are counted directly, so the total time complexity is O(log^2 n).

Space Complexity: O(log n).

A complete binary tree has height O(log n), and the recursive call stack follows at most that many levels.

Common Pitfalls

Pitfall 1: Not Leveraging Complete Binary Tree Properties

The most significant pitfall is treating the input like an arbitrary binary tree. A plain DFS that visits every node is correct for counting, but it misses the complete-tree property and violates the problem's requirement of running in less than O(n) time.

Why it's a problem: For large complete binary trees, visiting all n nodes becomes inefficient when we could use mathematical properties to calculate the count faster.

Solution: Use the complete binary tree properties to optimize:

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
      
        # Calculate left and right heights
        left_height = self.get_left_height(root)
        right_height = self.get_right_height(root)
      
        # If heights are equal, tree is perfect
        if left_height == right_height:
            return (2 ** left_height) - 1
      
        # Otherwise, recursively count
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
  
    def get_left_height(self, node):
        height = 0
        while node:
            height += 1
            node = node.left
        return height
  
    def get_right_height(self, node):
        height = 0
        while node:
            height += 1
            node = node.right
        return height

This optimized approach runs in O(log² n) time complexity by checking if subtrees are perfect binary trees.

Pitfall 2: Stack Overflow for Very Deep Trees

While less common for complete binary trees, the recursive approach can cause stack overflow for trees with extreme depth.

Why it's a problem: Python has a default recursion limit (usually around 1000), and very deep trees could exceed this limit.

Solution: Use an iterative approach with explicit stack:

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
      
        count = 0
        stack = [root]
      
        while stack:
            node = stack.pop()
            count += 1
          
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
      
        return count

Pitfall 3: Misunderstanding Complete Binary Tree Definition

Developers might incorrectly assume all levels are fully filled or implement unnecessary validation for tree completeness.

Why it's a problem: Adding unnecessary checks for tree completeness wastes computational resources when the problem guarantees the input is a complete binary tree.

Solution: Trust the problem constraints and focus on leveraging the complete tree properties rather than validating them. The optimal solution should use binary search on the last level to find the exact number of nodes in O(log² n) time.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering