---
title: "Strictly binary tree has 2n-1 nodes"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:strict-binary-tree-nodes-proof"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/strict-binary-tree-nodes-proof
site: BCT Engineering
---

# Strictly binary tree has 2n-1 nodes

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2073 Bhadra, 6 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/strict-binary-tree-nodes-proof
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Prove that strictly binary tree with n leaves contain 2n-1 nodes.

## Short answer

Let internal nodes be m, total nodes N = n + m. Each internal node has 2 children, so child links = 2m. Every node except root is a child, so child links = N-1 = n+m-1. Equate: 2m = n+m-1 ⇒ m = n-1, thus N = 2n-1.

## Answer

A **strictly binary tree** is a binary tree in which every node has either 0 or 2 children (no node has exactly one child).

**Claim:** a strictly binary tree with n leaves has 2n − 1 nodes.

#### Proof 1 (counting)
Let n be the number of leaves and m the number of non-leaf (internal) nodes, so the total is N = n + m.

- Every internal node has exactly 2 children, so the number of child links is 2m.
- Every node except the root is the child of exactly one node, so the number of child links is N − 1.

Therefore 2m = N − 1 = n + m − 1, giving m = n − 1.

Total nodes N = n + m = n + (n − 1) = **2n − 1**. ∎

#### Proof 2 (induction on n)
- Base case: n = 1. The tree is a single node (the root is a leaf), so N = 1 = 2(1) − 1. ✓
- Inductive step: assume every strictly binary tree with fewer than n leaves (n > 1) has 2k − 1 nodes for k leaves. Remove the root of the given tree; its two subtrees are strictly binary trees with n₁ and n₂ leaves, where n₁ + n₂ = n and n₁, n₂ ≥ 1. By hypothesis they have (2n₁ − 1) and (2n₂ − 1) nodes. Adding the root: N = 1 + (2n₁ − 1) + (2n₂ − 1) = 2(n₁ + n₂) − 1 = 2n − 1. ✓ ∎

Example: root with two leaves has n = 2 and 3 nodes = 2(2) − 1.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a strictly binary tree?
   A. Every node has exactly 1 child
   B. Every node has 0 or 2 children
   C. Every level is full
   D. Only leaves have 2 children
   Answer: B. No node may have exactly one child. (Key point: Definition)

2. In the counting proof, how many child links exist?
   A. m only
   B. 2N
   C. N + m
   D. 2m from internal nodes and N - 1 as all nodes except the root are children
   Answer: D. Both counts describe the same links, so 2m = N - 1. (Key point: Counting links)

3. What does the counting give for m?
   A. m = n + 1
   B. m = n - 1
   C. m = 2n
   D. m = n/2
   Answer: B. 2m = n + m - 1 gives m = n - 1. (Key point: Internal nodes)

4. How many nodes does a strictly binary tree with 5 leaves have?
   A. 10
   B. 11
   C. 7
   D. 9
   Answer: D. 2n - 1 = 9. (Key point: Total)

## Related in Data Structure and Algorithm

- [Binary tree traversals; preorder of BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-tree-traversal-methods-preorder) — Data Structure and Algorithm, chapter 6
- [Almost complete binary tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aalmost-complete-binary-tree) — Data Structure and Algorithm, chapter 6
- [Draw binary tree from preorder and inorder](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adraw-tree-from-preorder-inorder) — Data Structure and Algorithm, chapter 6
- [Almost complete tree; depth of complete tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aalmost-complete-depth-proof) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [CFG for aⁿb^(2n); parse tree](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-an-b2n-parse-tree) — Theory of Computation, chapter 3, asked 2×
- [Prove mean annual flood has 2.33-year return period](https://www.bctengineer.com/question.md?key=semester_5%2Fengineering_hydrology%3Agumbel-mean-flood-2-33yr) — Engineering Hydrology, chapter 6