Stack-based initialization creates unbalanced trees

I used your code as a reference for an implementation in PHP and I found that if the number of inputs is not a power of two the tree can become very unbalanced. The worst case of 2^n + 1 inputs results in a tree with 2^n elements in the left subtree and 1 element in the right.

I’ve solved this issue by recursively building the subtrees as follows:

protected function build_recursive($start=NULL, $end=NULL) {
    if( count($this->nodes) == 0 ) {
        throw new \Exception('Empty Node list.');
    }
    if( is_null($start) || is_null($end) ) {
        $start = 0;
        $end = count($this->nodes) - 1;
    }
    if( $end - $start == 0 ) {
        return $this->nodes[$start];
    } else {
        $mid   = $start + (int)floor( ($end - $start) / 2 );
        $left  = $this->build_recursive($start, $mid);
        $right = $this->build_recursive($mid+1, $end);
    }
    $node = new Node();
    $node->value   = $this->hash( $left->value . $right->value );
    $node->left    = $left;
    $node->right   = $right;
    $left->parent  = $node;
    $right->parent = $node;
    return $node;
}

For use cases such as yours, where there are always 2^n nodes in the tree, I think that your original approach is ideal. But for other use cases with variable inputs I think the above method is closer to the ideal approach for a balanced Merkle Tree.