Binary Tree and Overhead fraction Calculation 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 ?
 A: The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio.  According to the question I think you should use:
Number of leaves $= 0.5\cdot n$
Number of internal nodes$= 0.5\cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)
So now calculate total number of nodes its equal to
$$
(\text{leaves} +\text{internal nodes}+ \text{root})=0.5\cdot n+0.5\cdot n-1+1 = n
$$
Now according to the problem : 
Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5\cdot n-1+1)\cdot 2\cdot p=0.5\cdot n\cdot 2\cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2\cdot p$ because each note has $2$ pointers)
Space occupied by data$= 0.5\cdot n\cdot d $(d for you is again $4$ bytes)
Another thing I think is OVERHEAD fraction 
$$
\frac{\text{space taken by pointer}}{\text{space taken by data+space taken by pointer}}
$$
[not the reciprocal]
Therefore overhead fraction 
$$
=\frac{0.5\cdot n\cdot 2\cdot p}{(0.5\cdot n\cdot 2\cdot p)+(0.5\cdot n\cdot d)}=\frac{2\cdot p}{2\cdot p+d}
$$
Hope this helps.If I am wrong please tell me. :)
