user124148: I've been trying to understand this for a few days now.
I understand that the hashmerkleroot is the root node of a fully perfect binary tree. I also understand that the sha256d hashes would be the non-leaf/parent nodes of the tree and the sha256d hashes of the transactions would be the leaf nodes.
I also know that a fully perfect binary tree with 'x' leaves has 2x-1 nodes.
The question I'm trying to answer is what is the formula for the number of SHA256d hashes required to obtain the hashmerkleroot if the number of transactions to be hashed is 'x'? Is any of my understanding above incorrect?

user208: If the number of leaves is exactly a power of two (i.e., n = 2k), then the number of hashes performed is exactly n-1. This is easy to see: every hash operation takes two inputs, and reduces them to a single one. After n-1 operations, that means n nodes are reduced to 1, and that one is the Merkle root.
When the number of leaves is not a power of two, it's a bit more complicated. Whenever a "level" of the Merkle tree has an odd number of leaves, a hash operation is still performed for the last one, but it only takes one input. So every time this happens, it means an addition hash operation on top of the n-1 that are expected otherwise.
How often does that happen? Let's look at the level sizes for n=9..16 leaves:

9 → 5 → 3 → 2 → 1: 11 hashes (n - 1 + 3 odd levels)
10 → 5 → 3 → 2 → 1: 11 hashes (n - 1 + 2 odd levels)
11 → 6 → 3 → 2 → 1: 12 hashes (n - 1 + 2 odd levels)
12 → 6 → 3 → 2 → 1: 12 hashes (n - 1 + 1 odd level)
13 → 7 → 4 → 2 → 1: 14 hashes (n - 1 + 2 odd levels)
14 → 7 → 4 → 2 → 1: 14 hashes (n - 1 + 1 odd level)
15 → 8 → 4 → 2 → 1: 15 hashes (n - 1 + 1 odd level)
16 → 8 → 4 → 2 → 1: 15 hashes (n - 1 + 0 odd levels)

The number of odd levels is exactly equal to the number of 1 bits set in the binary representation of the difference between the number of leaves and the next power of two. For example, for n=11 leaves, the next power of two is 16, the difference between those is 5, which is written in binary as 1012, which has two 1s. Thus, the number of hashing operations is 11-1 + 2 = 12 hashes.
Without knowing anything about the structure of the number of leaves, a lower bound on the number of hashing operations is n-1, and an upper bound is n-1+log2(n-1).

124148: <p>I've been trying to understand this for a few days now.</p>
<p>I understand that the hashmerkleroot is the root node of a fully perfect binary tree. I also understand that the sha256d hashes would be the non-leaf/parent nodes of the tree and the sha256d hashes of the transactions would be the leaf nodes.</p>
<p>I also know that a fully perfect binary tree with 'x' leaves has 2x-1 nodes.</p>
<p>The question I'm trying to answer is what is the formula for the number of SHA256d hashes required to obtain the hashmerkleroot if the number of transactions to be hashed is 'x'? Is any of my understanding above incorrect?</p>
 208: <p>If the number of leaves is exactly a power of two (i.e., <em>n = 2<sup>k</sup></em>), then the number of hashes performed is exactly <em>n-1</em>. This is easy to see: every hash operation takes two inputs, and reduces them to a single one. After <em>n-1</em> operations, that means <em>n</em> nodes are reduced to <em>1</em>, and that one is the Merkle root.</p>
<p>When the number of leaves is not a power of two, it's a bit more complicated. Whenever a &quot;level&quot; of the Merkle tree has an odd number of leaves, a hash operation is still performed for the last one, but it only takes one input. So every time this happens, it means an addition hash operation on top of the <em>n-1</em> that are expected otherwise.</p>
<p>How often does that happen? Let's look at the level sizes for <em>n=9..16</em> leaves:</p>
<ul>
<li><em>9 → 5 → 3 → 2 → 1</em>: <em>11</em> hashes (<em>n - 1</em> + <em>3</em> odd levels)</li>
<li><em>10 → 5 → 3 → 2 → 1</em>: <em>11</em> hashes (<em>n - 1</em> + <em>2</em> odd levels)</li>
<li><em>11 → 6 → 3 → 2 → 1</em>: <em>12</em> hashes (<em>n - 1</em> + <em>2</em> odd levels)</li>
<li><em>12 → 6 → 3 → 2 → 1</em>: <em>12</em> hashes (<em>n - 1</em> + <em>1</em> odd level)</li>
<li><em>13 → 7 → 4 → 2 → 1</em>: <em>14</em> hashes (<em>n - 1</em> + <em>2</em> odd levels)</li>
<li><em>14 → 7 → 4 → 2 → 1</em>: <em>14</em> hashes (<em>n - 1</em> + <em>1</em> odd level)</li>
<li><em>15 → 8 → 4 → 2 → 1</em>: <em>15</em> hashes (<em>n - 1</em> + <em>1</em> odd level)</li>
<li><em>16 → 8 → 4 → 2 → 1</em>: <em>15</em> hashes (<em>n - 1</em> + <em>0</em> odd levels)</li>
</ul>
<p>The number of odd levels is exactly equal to the number of <em>1</em> bits set in the binary representation of the difference between the number of leaves and the next power of two. For example, for <em>n=11</em> leaves, the next power of two is <em>16</em>, the difference between those is <em>5</em>, which is written in binary as <em>101<sub>2</sub></em>, which has two <em>1</em>s. Thus, the number of hashing operations is <em>11-1 + 2 = 12</em> hashes.</p>
<p>Without knowing anything about the structure of the number of leaves, a lower bound on the number of hashing operations is <em>n-1</em>, and an upper bound is <em>n-1+log<sub>2</sub>(n-1)</em>.</p>
