i am trying to create a merkle tree that can handle both odd and even numbers of leaves, such that any time that there is no right pair to an element, i just want to carry that leaf one layer up. But i got a failed test for the odd numbers of leaves when ever try my all.
The code should past the below guidlines
expected 'Hash(Hash(A + B) + Hash(C + C))' to equal 'Hash(Hash(A + B) + C)'
should create a root from five leaves: [A,B,C,D,E]
expected 'Hash(Hash(Hash(A + B) + Hash(C + D)) …' to equal 'Hash(Hash(Hash(A + B) + Hash(C + D)) …'
should create a root from seven leaves: [A,B,C,D,E,F,G]
expected expected 'Hash(Hash(Hash(A + B) + Hash(C + D)) …' to equal 'Hash(Hash(Hash(A + B) + Hash(C + D)) …'
class MerkleTree {
constructor(leaves, concat) {
this.leaves = leaves;
this.concat = concat;
this.root = this.buildTree(leaves);
}
buildTree(nodes) {
if (nodes.length === 1) {
return nodes[0];
}
// Any time that there is no right pair to an element, i just want to carry that leaf one layer up:
// Root
// / \
// AB C
// / \ |
// A B C
// if nodes are odd, duplicate the last node and carry it a step up
// is is what i have done
if(nodes.length % 2 !== 0){
nodes.push(nodes[nodes.length - 1])
}
const newLevel = [];
for (let i = 0; i < nodes.length; i += 2) {
const left = nodes[i];
const right = nodes[i + 1];
const concatenated = this.concat(left, right);
newLevel.push(concatenated);
}
return this.buildTree(newLevel);
}
getRoot() {
return this.root;
}
}
module.exports = MerkleTree;