# 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)=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.

• "$f(h)=f(h)÷2$" Well, that can only be true if $f(h)=0$. Did you mean to write something else? Rather than writing "Correction:", please just edit your question so it just says whatever it should have done. Having a "wrong version" and a "right version" of hte question is just confusing and anybody who cares about how the question has changed over time can just look at the edit history. Jun 4, 2018 at 14:15

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.

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