Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on $n$ nodes:
2) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.
Above is a question from Steven Skiena Algorithm Design Manual. The answer on the wiki says:
In a full tree, given $n$ leaf nodes, there are $n-1$ internal nodes. Both leaf and internal nodes are worth $4$ bytes: $\dfrac{4 n} {4 n + 4 (n-1)} = \dfrac{4 n}{4(n + n -1)} = n / (2 n - 1)$, this approaches $1/2$ as $n$ gets large.
I dont understand above explanation since we are given $n$ nodes. How can you say n leaf nodes?
I calculated it in a different way. Assume we have a balanced binary tree. Let $L$ be number of leaf nodes. Then number of internal nodes is $L-1$. $$L + L-1 = n$$ $$L =n+1/2$$
$$L-1 =n-1/2$$
We can now calculate the overhead fraction as:
$$\dfrac{4(n+1/2) }{4(n+1/2) + 4(n-1/2)} $$
$$\dfrac{(n+1/2) }{(n+1/2) + (n-1/2)} $$
$$(n+1) / 2n $$
Can some help me figure out if my answer is correct ?