Are bitcoin Merkle trees always binary? I've been doing a lot of research about bitcoin, trying to understand it at the bit &amp; byte level.

I was wondering about the lookup efficiency of the Merkle tree.

I haven't found any evidence that Merkle trees are mandatory binary, which would allow a O(log2 n) lookup algorithm.

If a node may have an arbitrary number of children, then the lookup function would have a O(logK n * K), where K is the maximum number of allowed child nodes (as far as I remember).
Merkle trees in general can have more child nodes, but the Merkle tree for transactional data in Bitcoin is a binary tree.

&quot;Merkle trees are binary trees of hashes.&quot; –Bitcoin-Wiki Protocol Documentation
&quot;From these txids, the merkle tree is constructed by pairing each txid with one other txid and then hashing them together.&quot; –Developer Guide: Transaction Data

This has the advantage that only a list of root, log2(n) hash partners and the index of the transaction are sufficient to reconstruct a Merkle branch, allowing Simplified Payment Verification with much less data than the complete block.
If I am not mistaken, the binary format minimizes the amount of hashes that need to be transferred for full reconstruction of the Merkle branch, e.g. for 16 transactions

binary tree: root + 4*1 hashpartners + txid + position
three children tree: root + 3*2 hashpartners + txid + position
four children tree: root + 2*3 hashpartners + txid + position

Lookup is likely less of an issue than the wish to minimize bandwidth usage.
Yes, I'm committing the fallacy of &quot;proof by example&quot; here. ;)