Skip to main content
3 of 3
deleted 264 characters in body

Recursive relations in binary trees

I have an exercise in my algorithm's Course for which I have the correction but do not understand it.

1.Exercise .

Let Th be a full binary three of height h(meaning all the levels all completely full).

(1.a) : Let f(h) be the number of leaves of Th(nodes of the last level). Establish a relation for f(h) and solve it recursively. Give the exact expression for f(h) in terms of h, and the asymptote expression (in Big-O notation)

Correction

f(h)=2f(h-1) for h >= 1 and f(0) =1.
f(h)=2
f(h-1)=4f(h-2)=8f(h-3)=...=2^hf(h-h)=2^hf(0) =2^h.
Complexity : O(2^h)

I simply do not understand why h-1. Because suppose we have a full binary tree with h=2 . If h=2, then number of leaves = 4 . Applying the correction resolution:
f(2) = 2f(2-1) = 2f(1) = 2, which is different from the number of leaves, which is 4.