Show problems as
Classic problem #222MediumBinary SearchBit ManipulationTreeBinary Tree

Count Complete Tree Nodes

Real-world version: Counting the Chute Junctions
Tracked in this browser only
Read Count Complete Tree Nodes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstValidation & Properties · Binary Trees & BST, animated step by step

A mail room sorts parcels through a chute that splits in two at every junction. The chute is built to a strict pattern: counting the top junction as level 0, every level except the deepest one is filled with junctions, and on the deepest level the junctions are packed against the left with nothing to the right of them.

The layout comes to you as layout, a slot listing padded out to a full triangle. If the chute has h levels then layout has exactly 2^h - 1 slots. Slot 0 holds the top junction, and for any slot i the two slots below it are 2*i + 1 and 2*i + 2. A slot holding a number carries a junction, and that number is the junction's stencilled label. A slot holding null is empty. When the chute has no junctions at all, layout is empty.

Return how many junctions the chute has.

Labels carry no information about position and may repeat, and a junction may be labelled 0. Aim to answer in a number of steps that grows with the square of the level count rather than with the junction count, so reading every slot is more work than the pattern demands.

Examples

Example 1

Input
layout = [1, 2, 3, 4, 5, null, null]
Output
5

The listing is padded to seven slots for a three-level chute. Slots 0 through 4 carry junctions and the last two are empty.

Example 2

Input
layout = [1, 2, 3, 4, 5, 6, 7]
Output
7

Every slot of this three-level listing carries a junction, and the deepest level is full.

Example 3

Input
layout = [7]
Output
1

A single level with a single slot, so the chute has one junction, stencilled 7.

Example 4

Input
layout = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, null, null, null]
Output
12

Four levels, so the listing is padded to fifteen slots. Twelve of them carry junctions, packed against the left of the deepest level.

Example 5

Input
layout = [0, 0, 0, 0, 0, 0, null]
Output
6

Six of the seven slots carry junctions, every one of them stencilled 0, and only the final slot is empty.

Constraints

  • The number of junctions is in the range [0, 5 * 10^4].
  • 0 <= junction label <= 5 * 10^4
  • layout.length == 0 when there are no junctions, otherwise layout.length == 2^h - 1 for the chute's level count h.
  • The chute always follows the pattern: only the deepest level may be short, and it is packed to the left.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_nodes(layout: list[int | None]) -> int:
Java
public int countNodes(Integer[] layout)

More on the same topics