Recursive relations in binary trees

Question

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)=2*f(h-1) for h >= 1 and f(0) =1.
f(h)=2*f(h-1)=4*f(h-2)=8*f(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) = 2*f(2-1) = 2*f(1) = 2, which is different from the number of leaves, which is 4.

Answer 1

In a binary full tree, if in the level i there is n nodes then in the level i+1 there is 2n nodes, because each node produce 2 child.

So if you think about the nodes at every level, if you have k nodes in the h level, then k = 2*k' where k' is the number of nodes in level h-1, correct?

then you can write a recursion like the recursion in correction.

Regarding your example, there is a small mistake:

if we have a full binary tree with h = 2 then the recursion calculate the correct value because: f(2) = 2*f(1) = 2*2 = 4 because f(1) = 2*f(0) and f(0)=1 for base case.

Answer 2

I think you're just confused about the definition of "height". You write that you expect $f(2)=4$, where $f(h)$ is the number of leaves when the height is $h$. A full binary tree with four leaves looks like this:

     o
   /   \
  o     o
 / \   / \
o   o o   o

So, in this case, you're taking the height to be the number of edges between the root and a leaf, and a tree of height $h$ has $h+1$ levels of nodes.

But you also write $f(2) = 2f(2-1) = 2f(1) = 2$, implying that $f(1)=1$. A full binary tree with only one leaf looks like this:

     o

However, that tree has one level of nodes, so it has height zero. The height $1$ tree is

     o
    / \
   o   o

so we see that $f(2) = 2f(2-1) = 2\times 2 = 4$, as expected. Perhaps you were thinking of the following tree, which has one leaf and height $1$, but isn't a full binary tree.

     o
     |
     o