In CLRS page 158, on binary trees, the author states:
I'm having a hard time with the upper bounds of the number of nodes at a given height.
The total number of nodes is as follows:
$\sum_{i=0}^{k-1} 2^{i}$
Where $k$ is the depth of the tree, the sum of this geometric series, and total number of nodes is $n = 2^{k+1} - 1$.
For a given height in the tree, in my mind the maximum possible number of nodes at that level occurs when it is a full binary tree, and the number of nodes on a given level in a full binary tree is $2^{h-1}$ (per the geometric sum).
There is an excercise in the book around this, and I've even looked at a solution for it but I'm totally unconvinced as to how to arrive at:
$\frac{n}{2^{h+1}}$
Can anyone give me a pointer?
Thanks!