Merkle Tree that should handle both odd and even numbers of leaves

38 Views Asked by At

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;
0

There are 0 best solutions below