Also, the tree can be based on any underlying hash function, so the root hash can be literally "just" a SHA256 hash, but instead of hashing the whole file, it hashes a list of hashes.
You don't even need to store those intermediate nodes! They must be recomputed on-the-fly to verify the root hash anyway.
Last, but not least, the temporary space required is logarithmic in the size of the data, typically with a large exponent, so in practice this all fits on the stack. No heap memory allocations required, compatible with embedded devices, and can re-use cryptographic acceleration primitives like the AES-NI instruction set.
Conversely, tree-based hash constructions allow:
- Parallel generation and verification.
- Incremental repair of partially corrupted data.
- Extension of an existing hash (efficient append & prepend).
- Patricia hashes also allow efficient mutation in the middle of the data.
- Various deduplication and efficient incremental sync scenarios.