Implement and Explain a Merkle Tree

You are handed the assignment of implementing a Merkle tree, but no part of its interface has been settled yet. Before a single line of code is written, your task is to establish the contract that the implementation will be judged against.

Do not jump ahead to an implementation. Instead, resolve the open questions one by one: how the tree gets built from the supplied input, which hashing scheme applies and how values are encoded and combined at each level, whether the design is also expected to support inclusion proofs or allow existing entries to be modified, which boundary situations the code must cope with, and what cost bounds each operation is required to satisfy.

For each decision, spell out what you would want confirmed by the interviewer, what you would settle yourself, and the reasoning or trade-off behind that choice. Deliverable: the clarified contract only — no code.

Constraints:

• The tree-construction path from the input data must be covered.
• The hashing scheme must be pinned down, including leaf hashing versus internal-node hashing, encoding of values, and the order in which children are combined.
• Any optional capabilities — proof generation, entry modification, or both — must be stated explicitly as in scope or out of scope.
• Boundary situations the implementation must handle are to be enumerated.
• The time and space bounds expected of each operation are to be made explicit.