I am not familiar with the Amazon use case mentioned but a Merkle Tree in general only requires you to compute the hashes of the nodes in the tree that are in t

I am not familiar with the Amazon use case mentioned but a Merkle Tree in general only requires you to compute the hashes of the nodes in the tree that are in the path from the leaf node that you are trying to verify to the root node. This critical path is sometimes called the Merkle Path and gives you the missing information to calculate the resulting hash at each level of the tree. Essentially this 'rehashing' process rebuilds a portion of the tree until you reach the root and if the resulting hash matches the known Merkle Root then the content is valid. The benefit here is that you only need to do log2(n) calculations where n is the number of leaf nodes in the Merkle Tree. The image on this SE answer shows the concept well: https://bitcoin.stackexchange.com/a/50680 https://bitcoin.stackexchange.com/a/50680