Yes, and in fact, transactions of 1 MB are ridiculous, because they could easily be replaced by a tree structure of smaller transactions, changing the N^2 into N log N.
How about CoinJoin transactions? Is there a way to replace such transactions with tree structures of transactions in a safe, trustless way?
In bitcoin, there is no way to do CoinJoin trustlessly - at least at the protocol level. But the tree structure of doing CoinJoin trustlessly is exactly what is done in DASH. I think each step mixes 16 at a time or something of the kind (long time ago I read their whitepaper). The trustlessness comes from the collateral that masternodes need to provide in doing so. DASH has deep down, the bitcoin code, because it is a bitcoin code fork.
Of course, this is trustless concerning the safety of one's funds, not concerning the anonymity: the set of masternodes knows which funds went where ; but that's always the case of the entity that makes the coinjoin transaction.