Oppgave 1 a)

	A	B	C	D	E	F
Komplett	Nei	Nei	Nei	Nei	Ja	Nei
Perfekt	Nei	Nei	Nei	Nei	Nei	Nei
Fullt	Ja	Ja	Nei	Nei	Ja	Nei
Høyde	3	3	3	3	3	3
Bladnode	6	6	6	4	7	4
Turneringstre	Nei	Nei	Nei	Nei	Ja	Nei

Oppgave 2

Et perfekt tre med høyde 3 (til venstre) og et komplett tre med 10 noder (til høyre):

Et komplett tre med 20 noder:

Oppgave 3

Det er 2 forskjellige fulle trær med 5 noder og 5 med 7 noder.

La et fullt tre ha n noder. Det går en kant ned til hver node unntatt rotnoden. Dvs. treet har n - 1 kanter. Alle indre noder har to barn, dvs. alle noder som det går kanter ut fra (nedover fra) har to utgående kanter. Dermed må antallet kanter n - 1 være delelig med 2, dvs. n er et odde tall.

Oppgave 4

La n >= 1 og la k være det største heltallet slik at 2^k <= n. Dermed blir 2^k <= n < 2^k+1.

Eksempel: Hvis n = 25, vil k = 4 siden 2⁴ <= 25 < 2⁵.

Vi får k <= log₂(n) < k + 1 og dermed   ⌊log₂(n)⌋ = k.

Videre får vi at 2^k < n + 1 <= 2^k+1 og dermed at  k < log₂(n+1) <= k + 1. Det betyr at
 ⌈log₂(n+1)⌉ - 1 = k + 1 - 1 = k.

Konklusjon:   ⌊log₂(n)⌋ = k = ⌈log₂(n+1)⌉ - 1