Proof of non-membership on a Merkle tree? Assume a user $U$ and a server $S$. $U$ uploads its data and wants later to perform an authenticity check. It also sends a Merkle tree to the server. Let’s say we would like $U$ to ask for a specific element in the tree. $S$ then returns the leaf node and the path to the root that would allow $U$ to verify. This acts as a proof of completeness.

In the case an element is not part of the Merkle tree, how the server can prove the non-membership proof?
If you are not worried about revealing information, then you can commit to the set of data items in one Merkle tree, and to the frontier of that set in another Merkle tree. A frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is inside the set you work with the first tree, and in order to prove that it is not you work with the second tree. 

However, I strongly recommend that you read this paper on Zero-Knowledge Sets by Micali, Rabin and Kilian. First, the notion of a frontier mentioned above is defined. Second, they provide a formal definition and analysis. Third, they achieve something much stronger which is that nothing but the fact that the element is in or is not in the set is revealed (not even the size of the set). There was some follow up work on zero-knowledge sets as well, but you can find them easily by Googling.