← DiffPush

Count Nodes in a Complete Binary Tree

DiffPush Tier Binary Trees · Hard O(log^2 n) · O(log n)

The Occupancy Census in the Parking Silo

An automated parking silo stacks cars in a complete binary layout: every floor is fully occupied except possibly the last, whose cars hug the left ramp. The counter hardware broke, so the auditor must derive the exact car count from the layout map alone — and the audit SLA forbids walking every single bay. Exploit the guaranteed fullness instead.

Input: The root of a complete binary tree given as a level-order array (null marks a missing child).

Output: Return the total number of nodes in the tree.

Constraints

• 1 <= number of nodes <= 5 * 10^4
• -10^4 <= node value <= 10^4
• The tree is complete

Examples

Example 1

Input: {"tree":[1,2,3,4,5,6]}
Output: 6
Two full levels plus three nodes hugging the left on the last level.

Example 2

Input: {"tree":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]}
Output: 15
A perfect tree of four levels holds 2^4 - 1 = 15 nodes.

Solve this in your browser →

Also on LeetCode ↗