I'm reading the Introduction to Algorithms book and there's the following recurrence relation
$$ T(n) = \begin{cases} c, & n = 1 \\ 2T(n/2) + cn, & n > 1 \end{cases} $$
$c$ is just a constant.
So, the author wants to show that the solution is $\mathcal{O}(nlgn)$ and for this purpose he draws a tree.
Could someone please explain me why the author considers $cn$ as the root of the tree? I expected that the root is $T(n)$ and it has two subtrees and one leaf ($cn$).
On
Initially suppose that n is a power of 2 (this will make the computation easier), ie $n=2^k$.
Then $T(n)=2T(n/2)+cn$, and we may replace $T(n/2)$ with $2T(n/4)+\frac{cn}{2}$, we get: $T(n)=4T(n/4)+2\frac{cn}{2}+cn$. Again, one may replace $T(n/4)$ with $2T(n/8)+c\frac{n}{4}$. This justifies the binary tree you have mentioned. In general, after repeating this $k$ times we get that: $$T(n)=4T(n/4)+2\frac{cn}{2}+cn=...=2^kT(1)+2^{k-1}\frac{cn}{2^{k-1}}+...+2\frac{cn}{2}+cn=2^kT(1)+kcn$$ Replacing k with $log_2(n)$, and since $T(1)=O(1)$, we get that $T(n)=O(nlog(n))$, as you mentioned.
$cn$ is work in root itself, not including work in subtrees. Total work $T(n)$ will be sum of work in all nodes in tree.
Standard example: lets say that to process array of length $n$, you need to process $2$ arrays of length $n/2$ and then do $cn$ additional operations. Then in root node there will be this $cn$ additional operations, and subtrees will correspond to processing arrays of length $n/2$. And so on - in every node we write only this "additional operations", and processing of smaller parts goes to subtrees.