In those cases where all leaves of a Merkle tree are already known at the time of construction (which is currently always the case for us), the tree's branch and root calculation can be delayed until after all leaves are written. This avoids recalculating the right-most path to the root every time a new leaf is appended to the tree.

Also, the vector holding the tree's nodes can be pre-allocated if the number of leaves is known.

To calculate the tree's branches after the leaves are written, the branches need to be walked layer by later starting at the leaf layer. For this one needs to make use of the indexing scheme used by the astria-merkle crate:

According the indexing scheme the trailing set bits indicate the depth of the subtree. So the root for a tree of depth D has a binary representation of 011...1 with D-1 ones. This extends to every subtree. This means we should be able to walk the tree by "roots-of-subtrees" by fixing the number of trailing 1s at each level.