# Comparing n-multiple amount of merkle trees?

I would like to know what best steps are there in finding differences between a high order amount of merkle tree's or if a better associative structure should be used.

I ask this questions because while i have found on comparing two trees for differences i have not found any specifics on comparing n amount at the same time (100-200 for ex).

While i would imagine a sequential validation process from one tree to the next, my question would be if there are any general way to do so.

While I originally looked into what would require the use of some Tree Topology or use of Bloom Filters, I asked a friend on this problem. He gave me a more practical solution:

1. Sort each Tree by Leaves Seperately
2. Then you put each result in heaps - sort of like a merge step of the quick sort algorithm.
3. You then take the First Heap from the first tree and compare it with the first heaps from the other trees.

• If all heaps match, pop all the heaps and you have a leaf present in all of the trees

• If the first heap is larger than any given heap, pop it - it doesn't match all the trees. Continue popping from that heap until you find a matching heap, or...

• If the first heap is smaller than any given heap, pop all of the previously checked heaps - all of them contain a leaf that is not present in all of the trees

• Repeat until one of the heaps is empty

This solution has a linear complexity - you will compare each leaf about 1 time.