Proof of membership and non-membership in Merkle tree (Hash-tree)

Question

If we just know the Merkle root and the data block and we want to know this block is a member of this merkle tree. We need to know all the blocks from the leaf to the root that are associated with data block and we ignore the rest.

But how and whats the point of this?.

If the system is doing so much work finding the blocks associated with this data block we have.It might as well directly do a simple search and find out whether the given data block exists in the first place.

This becomes even more confusing when we use a sorted merkle tree for proof of non-membership. Please explain me what's the concept and what's going on in these two proofs

Answer 1

If you don't use a merkle tree then checking membership is an O(n) operation, as opposed to O(log n) with a merkle tree. Instead of going through each item in the set, you walk up one branch of the merkle tree which has O(log n) depth.

Though, without sorting, proving non-membership still requires O(n) steps. Sorting makes it possible to prove non-membership by only looking at the leaf nodes that would be adjacent to the non-element.

I found this short summary here that's really useful.