Count Complete Tree Nodes

easyPROTrees & GraphsGoogle DSA

Given the root of a complete binary tree (as a level-order array), return the number of nodes.

A complete binary tree has every level fully filled except possibly the last, which is filled from left to right.

Example

Input

1,2,3,4,5,6

Output

Reasoning

Input: root is the top node of a complete binary tree. The sample 1,2,3,4,5,6 lists its values level by level, left to right; each node links to at most a left and a right child.
The tree: level 1 holds 1; level 2 holds 2 and 3; level 3 holds 4, 5 under 2 and 6 as the left child of 3. The right child slot of 3 is empty.
The math: a full level $k$ holds $2^{k-1}$ nodes, so the two full top levels contribute $2^0 + 2^1 = 2^2 - 1 = 3$ . The last level could hold $2^2 = 4$ nodes but has only $3$ , packed to the left.
Output: $3 + 3 =$ 6, a single integer. Node values play no part; only the shape matters.
Notice that "complete" pins the shape down: the count always lies between $2^{h-1}$ and $2^h - 1$ for a tree of height $h$ (here between $4$ and $7$ ). An empty tree, with no root at all, has $0$ nodes.

Constraints

0 <= number of nodes <= 5 * 10^4
0 <= Node.val <= 5 * 10^4

More from Google DSA

Time Based Key-Value Storemedium Moving Average from Data Streameasy Snapshot Arraymedium LRU Cachemedium Find Peak Elementeasy

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results

Count Complete Tree Nodes

Example

Constraints

More from Google DSA

Background Knowledge

Continue the full explanation

Editor locked