Sparse Merkle Tree

A Merkle tree stores data at the leaves and each internal node stores the hash of the concatenation of its children's hashes. Implement a Sparse Merkle Tree (SMT) of depth D that conceptually has 2^D leaves, but only allocates nodes that have been touched.

For this problem, use a simplified hash function: H(x) = x if x is non-empty H("") = "0" if x is empty

Default hashes for empty subtrees: defaultHash(0) = H("") = "0" defaultHash(h) = H(defaultHash(h-1) + defaultHash(h-1)) (for h >= 1)

So defaultHash(1) = "00", defaultHash(2) = "0000", defaultHash(3) = "00000000", etc.

Required interface (called via Solution):

| Method | Description | |--------|-------------| | Solution(depth) | Initialize an empty tree of given depth. All 2^depth leaves are conceptually empty. | | insert(index, value) | Set the leaf at 0-based index to value. If value is empty, store the leaf as "0" (i.e. H("")). Must be O(D). | | rootHash() | Return the hash of the root after all insertions so far. O(1). |

Sparseness: do not allocate all 2^D leaves. Only nodes on the path from inserted leaves to the root should exist; missing nodes use their defaultHash.

Example walk-through (depth = 3):

Initial tree is all empty. rootHash() = defaultHash(3) = "00000000".

Now insert(2, "A"):

• leaf hash at index 2 becomes "A" (other leaves use defaultHash(0) = "0")
• level 1 node above leaves 2,3: H("A" + "0") = "A0"
• level 1 node above leaves 0,1: defaultHash(1) = "00"
• level 2 node above leaves 0..3: H("00" + "A0") = "00A0"
• level 2 node above leaves 4..7: defaultHash(2) = "0000"
• root: H("00A0" + "0000") = "00A00000"

Then insert(5, "B"):

• root becomes "00A00B00" (similar walk).

Then insert(7, ""):

• value "" is stored as "0" (the H-of-empty rule), which equals the default — no change to the root.

Final rootHash() = "00A00B00".