1. The problem asks for the number of nodes at height $h$ in a complete binary tree $T$ of size $n$, where the last level is filled from left to right.
2. Recall: height of a node is the number of edges from that node to the deepest leaf in its subtree, and leaves have height 0.
3. In a complete binary tree, nodes are filled level by level, left to right, and the height of the tree is $H=\lfloor \log_2 n \rfloor$.
4. The number of nodes at height $h$ corresponds to the number of nodes on level $L = H - h$, where levels are indexed from 0 at the root.
5. Let $L = H - h$. The maximum number of nodes at level $L$ in a perfect binary tree is $2^L$.
6. However, since the last level might not be full, the actual number of nodes at level $L$ can be limited by $n - (2^{H} - 1)$, the number of nodes in the last level.
7. Hence, the number of nodes at height $h$ in $T$ is:
$$\text{nodes}(h) = \max\left(0, \min\left(2^{H - h}, n - (2^{H} - 1) \right) \right)$$
8. More explicitly, for $h \leq H$:
$$\text{nodes}(h) = \begin{cases}
2^{H-h}, & \text{if } h < H \\
n - (2^{H} - 1), & \text{if } h = 0 \text{ (the last level) }
\end{cases}$$
9. When $h > H$, nodes at that height do not exist, so the number is 0.
Therefore, the function specifying the number of nodes at height $h$ in $T$ is:
$$\text{nodes}(h) = \max\left(0, \min\left(2^{H - h}, n - (2^{H} - 1)\right)\right)\quad\text{where } H = \lfloor \log_2 n \rfloor.$$
Nodes At Height
Step-by-step solutions with LaTeX - clean, fast, and student-friendly.