Merkle Tree space complexity When searching by using the Merkle tree, the time complexity is $\mathcal O(\log n)$ but I don't understand how space complexity is $\mathcal O(n)$. In my opinion, it should be also $\mathcal O(\log n)$. Can somebody explain it to me?
For simplicity assume that the Merkle tree is a perfect binary tree. Let the number of data blocks is $n$ which are linked to the leaf nodes. Therefore the total number of tree nodes are $|nodes| = n + n/2+ \cdots +1$. If we assume that $n =2^k$ for simplicity than $$|nodes| = 1 + 2 + 2^2 + \cdots + 2^k = \frac{2^k-1}{2-1} = 2^k-1 = n-1.$$ In total, we have $n+ n -1 $ nodes, that is together with the data blocks. As a result the number of nodes are $\mathcal{O}(n)$.

In another approach, you can consider the height of the tree as the search complexity, $h = c \log n$ then the maximum number of a binary tree with $h$ is $2^h-1 = 2^{c \log n}-1 = n 2^c-1 \in \mathcal{O}(n)$. Adding the data block will not change the complexity.

Note: In a complete binary tree, if we say that the root is level 1 then the $i$-th level contains $2^{i-1}$ nodes. Each level will contain a double of the previous level.