SME
Data Structures & Algorithms
Trees and graphs
Use this for “What is the least height of a binary tree with 100 nodes? How many nodes and leaves can a tree of height 6 hold?”
Diagram
Filled level by level, 100 nodes reach level 6: hₘᵢₙ = ⌈log₂(100 + 1)⌉ − 1 = 6.
A tree of height 6 holds at most 2⁷ − 1 = 127 nodes, 64 of them leaves.
This is an example. Type your own values to start a new problem.
hₘᵢₙ
=
⌈log₂(
n
+
1)⌉
−
1
Nₕ
=
2
+
1
−
1
Lₕ
=
2
Formulas
hₘᵢₙ
=
⌈log₂(
n
+
1)⌉
−
1
6 = ⌈log₂(100 + 1)⌉ − 1
Nₕ
=
2
h
+ 1
−
1
127
=
2
6 + 1
−
1
Lₕ
=
2
h
64
=
2
6
Assumptions
•
Height counts edges from the root down, so a tree of one node has height 0.
•
Each node has at most two children, so level k holds at most 2ᵏ nodes.
•
The least height comes from filling every level before starting the next.
Step-by-step
WE KNOW
n = 100, h = 6
FIND
least height (hₘᵢₙ), most nodes at h (Nₕ), most leaves at h (Lₕ)
Step 1 · Find least height (hₘᵢₙ)
Use hₘᵢₙ = ⌈log₂(n + 1)⌉ − 1
Filled
level
by
level,
a
tree
of
height
h
holds
up
to
2
h
+ 1
−
1
nodes,
so
take
the
smallest
h
with
room
for
n
.
hₘᵢₙ = ⌈log₂(100 + 1)⌉ − 1
⌈log₂
101⌉
=
7,
since
2
6
=
64
<
101
≤
128
=
2
7
hₘᵢₙ = 6
Step 2 · Find most nodes at h (Nₕ)
Use Nₕ = 2ʰ⁺¹ − 1
Levels
0
to
h
hold
1
+
2
+
4
+
…
+
2ʰ
nodes,
one
less
than
the
next
power
of
2.
Nₕ
=
2
6 + 1
−
1
Nₕ
=
2
7
−
1
Nₕ = 128 − 1
Nₕ = 127
Step 3 · Find most leaves at h (Lₕ)
Use Lₕ = 2ʰ
The
last
level
doubles
h
times
from
the
root.
Lₕ
=
2
6
Lₕ = 64
Check
Put the numbers back in. Both sides should match.
6 = ⌈log₂(100 + 1)⌉ − 1 ✓
127
=
2
6 + 1
−
1
✓
64
=
2
6
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Heap array indices
Use this for “A heap is stored in an array from index 0. What are the parent and children of the node at index 5?”
Adjacency matrix or list size
Use this for “An undirected graph has 1000 vertices and 5000 edges. How many cells does its adjacency matrix take, and how many entries its adjacency list?”
Preorder traversal of a search tree
Use this for “Insert 50, 30, 70, 20, 40, 60, 80 into an empty binary search tree. In what order does a preorder traversal visit the nodes?”