Sum-Product Networks (SPNs) are a recent class of probabilistic models which encode very large mixtures compactly by exploiting efficient reuse of computation in inference. Crucially, in SPNs the cost of inference scales linearly with the number of edges $E$ but the encoded mixture size $C$ can be exponentially larger than $E$. In this paper we obtain an efficient ($O(E)$) implementation of Expectation Maximization (EM) for SPNs which is the first to include EM updates both on mixture coefficients (corresponding to SPN weights) and mixture components (corresponding to SPN leaves). In particular, the update on mixture components translates to a weighted maximum likelihood problem on leaf distributions, and can be solved exactly when leaves are in the exponential family. This opens new application areas for SPNs, such as learning large mixtures of tree graphical models. We validate the algorithm on a synthetic but non trivial soft-parity distribution with $2^{n}$ modes encoded by a SPN with only $O(n)$ edges.