I have an exercise in my algorithm's Course for which I have the correction but do not understand it.
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)
f(h)=2*f(h-1) for h >= 1 and f(0) =1.
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) = 2*f(2-1) = 2*f(1) = 2, which is different from the number of leaves, which is 4.