Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum height

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Define a complete binary tree. from Lesson 4.2.1
• What does p->next = p->next->next do? from Lesson 3.4.5
• What is 1 + 2 + 4 + … + 2ʰ? from Lesson 0.2.2

1 · The Hook

🎣

A tournament with 64 teams needs how many rounds? How many matches in total? Binary trees answer such questions instantly with a handful of formulas, all coming from the fact that each level can at most double.

2 · Predict First

🤔

A binary tree has 20 leaves. How many of its nodes have exactly two children? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

19. In every binary tree, leaves = (nodes with two children) + 1, whatever the shape. (A 20-team knockout needs 19 matches.)

Nodes per level and per height

• Level i holds at most 2^i^ nodes (each level can at most double).
• A binary tree of height h has at most 1 + 2 + … + 2^h^ = 2^h+1^ − 1 nodes (perfect tree) and at least h + 1 nodes (a path).

Minimum and maximum height for n nodes

• Maximum height: n − 1 (skewed).
• Minimum height: the smallest h with 2^h+1^ − 1 ≥ n, i.e. h = ⌈log₂(n + 1)⌉ − 1 = ⌊log₂ n⌋. A complete tree achieves it. (n = 7 → 2; n = 8 → 3; n = 1000 → 9.)

n₀ = n₂ + 1

Let n₀, n₁, n₂ be the numbers of nodes with 0, 1, 2 children. Count edges two ways: edges = n − 1 = (n₀ + n₁ + n₂) − 1, and edges = (children counted from parents) = n₁ + 2n₂. Equating gives n₀ = n₂ + 1, independent of n₁.

More counts

• A strict binary tree with i internal nodes has i + 1 leaves and 2i + 1 nodes.
• A binary tree with n nodes has n + 1 NULL child pointers (2n pointer fields, n − 1 of them used by edges).
• With the nodes convention, replace h by h − 1 in every formula (max nodes 2^h^ − 1).

4 · Visual

n₀ = 4 leaves (8, 5, 6, 9), n₂ = 3 nodes with two children (1, 2, 3), n₁ = 2 (4, 7): n₀ = n₂ + 1 holds.

level   max nodes   running total (max nodes for height h)
  0         1            1
  1         2            3
  2         4            7
  3         8           15
  h        2^h       2^(h+1) - 1

Edge count:  n - 1  =  n1 + 2*n2      and   n = n0 + n1 + n2
             =>  n0 + n1 + n2 - 1 = n1 + 2*n2   =>   n0 = n2 + 1

Doubling per level gives the maximum counts; counting edges twice gives n₀ = n₂ + 1.

5 · Worked Examples

Example 1 Easy

What is the maximum number of nodes at level 5, and in a binary tree of height 5?

Solution

2⁵ = 32 at level 5; 2⁶ − 1 = 63 in total.

Example 2 Medium

What are the minimum and maximum heights of a binary tree with 100 nodes?

Solution

Minimum ⌊log₂ 100⌋ = 6 (2⁶ = 64 ≤ 100 < 128). Maximum n − 1 = 99.

Example 3 GATE

A binary tree has 30 nodes with exactly one child and 15 nodes with two children. How many leaves and how many nodes does it have?

Solution

n₀ = n₂ + 1 = 16; n = 16 + 30 + 15 = 61.

6 · GATE Traps

⚠️

• Max nodes for height h is 2ʰ⁺¹ − 1 with edges, 2ʰ − 1 with nodes: check the convention.
• n₀ = n₂ + 1 holds for every binary tree, but says nothing about n₁.
• Minimum height is ⌊log₂ n⌋, not ⌈log₂ n⌉ (for n = 8 both happen to be 3, for n = 7 they differ: 2 vs 3).
• A binary tree of n nodes has n + 1 NULL pointers.
• Level i can hold at most 2ⁱ nodes, but a level can be partly empty.

8 · Memory Hook

🧠

“Leaves outnumber twin-parents by one.” Every match in a knockout eliminates one team, so n teams need n − 1 matches.

9 · Connect the Dots

Lessons 4.2.1–4.2.2 described shapes and counts. A program must still store the nodes somewhere. Next lesson answers: how is a binary tree stored with pointers, and how can a complete tree be stored in a plain array with no pointers at all?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markn₀ = n₂ + 1

A binary tree has 25 nodes with two children. How many leaves does it have?

Numerical answer: ________

Q2NAT1 markMin height

What is the minimum height (edges) of a binary tree with 1000 nodes?

Numerical answer: ________

Q3MCQ1 markMax nodes

The maximum number of nodes in a binary tree of height h (edges convention) is:

• (A) 2ʰ − 1
• (B) 2ʰ
• (C) 2ʰ⁺¹ − 1
• (D) h + 1

Q4NAT2 marksNULL pointers

How many NULL child pointers does a linked binary tree with 50 nodes have?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true for every binary tree with n ≥ 1 nodes?

• (A) height ≥ ⌊log₂ n⌋
• (B) leaves = nodes with two children + 1
• (C) height ≤ n − 1
• (D) n₁ = n₀ − 1

11 · Rule Card

• Level i: ≤ 2ⁱ nodes; height h: h + 1 ≤ n ≤ 2ʰ⁺¹ − 1 (edges).
• n nodes: ⌊log₂ n⌋ ≤ height ≤ n − 1.
• n₀ = n₂ + 1; strict tree with i internal nodes: i + 1 leaves, 2i + 1 nodes.
• n + 1 NULL pointers.
• Nodes convention: replace h by h − 1.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

max nodes per level 2ⁱmax nodes 2ʰ⁺¹ − 1minimum height ⌊log₂ n⌋n₀ = n₂ + 1NULL pointers n + 1

13 · Answer Vault