Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to calculate the amount of elements in a Merkle tree given the number of leaf elements.

The number of elements at a given level n is equal to number of elements at a level n+1, divided by two and rounded up. The highest level are the leaf elements, and the root of the tree contains only one element.

I can calculate the value recursively without any problem, but I'd like to know if there is any formula that could give the result without recursion.

share|improve this question

1 Answer 1

If I understand you correctly, you're asking a question equivalent to "Given the number of leaf nodes, what's the total number of nodes in a binary tree?"

One special case -- the "perfect binary tree" -- occurs when you get a number of leaf nodes that is exactly some power of two -- n_leaves = 2^x. In that case, the total number of nodes is n_nodes = 2*n_leaves - 1.

I'm pretty sure that formula is true for any strictly binary tree -- i.e., a tree where every non-leaf node has exactly two children -- even ones that are terribly unbalanced. That's because every strictly binary graph can be created by starting with a single (leaf) node, and repeatedly adding a pair of nodes. At each step, a leaf in the graph is converted to a non-leaf node, and two leaves are added -- a net increase of one leaf node and one non-leaf node. Since we started with only a single root leaf node, the number of leaf nodes n_leaves is always exactly one more than the number of non-leaf nodes n_non_leaves. So the total number of nodes n_nodes = n_leaves + n_non_leaves in a strictly binary graph is always n_nodes = 2*n_leaves - 1.

Is your Merkle tree always a "strictly binary tree"?

EDIT:

For some reason I thought that, if there were an odd number of leaves in the tree, that the left-over hash (after all the other hashes were paired off) was passed up to the next level unchanged. You seem to be saying that the left-over hash is re-hashed to generate its part of the next level. It escapes me what is the point of re-hashing an internal hash with only one child, but I'm sure you have your reasons.

I'm assuming that the root node always has 2 or 0 children, never 1 child.

In the special case where the number of leaves has one fewer than some power of two -- n_leaves = 2^x - 1 -- then the internal graph of non-leaves looks exactly like the "perfect binary tree" that had 2^x leaves, so there are 2^x - 1 non-leaf nodes, so the total number of nodes is n_nodes = 2*n_leaves.

In the other extreme special case where the number of leaves is one greater than some power of two -- n_leaves = 2^x + 1 -- then the internal graph of non-leaves has one section that looks exactly like the "perfect binary tree" of 2^x leaves, plus a linear rail along the side that goes all the way up to the root. There are 2^x-1 non-leaf nodes in the "perfect binary tree" section. There are x+2 non-leaf nodes in the "linear rail" section (including the root node). So the total non-leaves is 2^x-1 + x+2 = 2^x+1+x = n_leaves + log2( n_leaves-1 ) = non_leaves. So the total number of nodes = leaves+non_leaves = 2*n_leaves + log2( n_leaves-1 ).

I'm pretty sure any other number of leaves will give something intermediate between these special cases -- a linear rail that runs only partially up the right side. It escapes me at the moment exactly how to calculate how many nodes will be in that linear rail. Perhaps just knowing the minimum and maximum range will be adequate for your application:

In all cases, 2*n_leaves - 1 <= n_nodes <= 2*n_leaves + log2( n_leaves-1 ).

share|improve this answer
    
According to ThePiachu’s description, it’s not strictly binary: all of the leaves are at the same level. –  Brian M. Scott Dec 10 '11 at 5:48
    
It is not a binary tree, as some nodes can have only one child. If the amount of nodes at a given level is odd, the level closer to the root will have exactly one node that has one child. –  ThePiachu Dec 10 '11 at 12:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.