Is Count Complete Tree Nodes easy or hard?

The problem is labeled Easy on LeetCode because the core idea is recognizing the structure of a complete binary tree. However, discovering the O(log² n) optimization instead of a full traversal can feel closer to a medium-level insight for many candidates.

Count Complete Tree Nodes Python/Java solution

Both Python and Java implementations typically compute subtree heights and apply recursion. The logic checks whether left and right heights are equal to determine if a subtree is perfect. If so, return 2^h - 1; otherwise recursively count nodes in both children.

How to solve Count Complete Tree Nodes in O(n)?

Traverse the tree using DFS or BFS and increment a counter for each visited node. This guarantees correctness for any binary tree and runs in O(n) time with O(h) recursion stack or O(n) queue space depending on the traversal method. It ignores the complete-tree optimization.

What is the best approach for Count Complete Tree Nodes?

The most common solution uses recursive height comparison. Compute the height of the leftmost and rightmost paths. If they match, the subtree is perfect and contains 2^h - 1 nodes. Otherwise recurse on the children. This runs in O(log² n) time because height computation and recursion both take O(log n).

Is Count Complete Tree Nodes asked at Google/Amazon/Meta?

Count Complete Tree Nodes frequently appears in interviews at large tech companies because it tests recognition of structural properties in trees. Instead of brute-force traversal, candidates are expected to detect perfect subtrees or apply binary search on the last level.

What data structure is used in Count Complete Tree Nodes?

The problem uses a binary tree, specifically a complete binary tree. Efficient solutions rely on properties of complete trees, such as predictable height and contiguous node placement on each level, combined with binary search or subtree height calculations.

What is the time complexity of Count Complete Tree Nodes?

The optimized solutions run in O(log² n) time. Each step computes subtree height or performs a node-existence check in O(log n), and the process repeats across O(log n) levels. A simple DFS or BFS traversal would take O(n) time instead.

Description Solution Video 13:39

222. Count Complete Tree Nodes

Medium72.6% acceptance7 companies

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1: