#222

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Count Complete Tree Nodes

Count Complete Tree Nodes efficiently by leveraging binary-tree traversal, exploiting completeness, and applying bit manipulation optimizations.

binary search bit manipulation tree binary tree

Problem Statement

Given a complete binary tree, return the total number of nodes present. Every level, except possibly the last, is fully filled, and nodes in the last level are positioned as far left as possible.

Your task is to design an algorithm that computes the count faster than O(n) by exploiting the tree's completeness, enabling efficient traversal and state checks for missing nodes.

Examples

Example 1

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

Output: 6

Example details omitted.

Example 2

Input: root = []

Output: 0

Example details omitted.

Example 3

Input: root = [1]

Output: 1

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.

Solution Approach

Recursive Height Comparison

Compute left and right subtree heights at each node. If heights match, the subtree is perfect, allowing direct calculation of its node count. Otherwise, recurse into left and right subtrees, summing counts efficiently.

Binary Search on Last Level

Determine the tree height and perform binary search on possible node positions in the last level. Use a helper function to check node existence via left/right traversal, counting only valid nodes without visiting all nodes.

Bit Manipulation for Existence Checks

Represent paths to nodes in the last level as binary numbers. Use bit shifts to navigate left or right from the root, efficiently validating node existence while avoiding unnecessary traversal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can reach O((log n)^2) due to height computations and binary searches on the last level. Space complexity is O(log n) from recursion stack, or O(1) if iterative traversal is used.

What Interviewers Usually Probe

Ask candidates to explain why naive traversal is not optimal for complete trees.
Probe if they can calculate subtree node counts using height differences.
Listen for recognition of binary search application on the last level of a complete tree.

Common Pitfalls or Variants

Common pitfalls

Failing to exploit tree completeness and scanning all nodes unnecessarily.
Miscomputing tree height or assuming all levels are completely filled.
Incorrectly handling empty trees or last-level node counts.

Follow-up variants

Count nodes in a perfect binary tree, simplifying the height comparison step.
Determine the number of leaf nodes only, focusing traversal on the last level.
Apply the approach to a k-ary complete tree with similar height-based optimizations.

FAQ

Why is binary search useful for counting nodes in a complete tree?

Binary search allows checking positions in the last level without traversing every node, leveraging the complete tree structure for efficiency.

Can this approach handle empty trees?

Yes, the algorithm correctly returns zero when the root is null, avoiding errors in height calculations.

Is recursion necessary for Count Complete Tree Nodes?

Recursion simplifies height-based calculations, but iterative methods with bit manipulation can achieve the same sublinear performance.

What is the time complexity of this solution?

The optimized approach runs in O((log n)^2) time due to recursive height checks combined with binary search on the last level.

How does bit manipulation improve last-level node checks?

Bit shifts represent paths from root to nodes, allowing fast left/right navigation to verify node existence without full traversal.

terminal

Solution

Solution 1: Recursion

We recursively traverse the entire tree and count the number of nodes.

1

2

3

4

5

6

7

8

9

10

11

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Solution 2: Binary Search

For this problem, we can also take advantage of the characteristics of a complete binary tree to design a faster algorithm.

1

2

3

4

5

6

7

8

9

10

11

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Continue Practicing

#226 invert binary tree #230 kth smallest element in a bst #235 lowest common ancestor of a binary search tree