Implement a Merkle Tree for Repository Contents

Problem Statement

Modern code editors and version control systems track workspace changes efficiently by representing file trees as Merkle trees (hash trees). In this structure, every file has a hash derived from its content, and every directory has a hash derived from the names and hashes of its immediate children. If two directory nodes share the same hash, their entire subtrees are guaranteed to be identical, allowing rapid change detection without scanning unchanged files.

Implement the class RepoMerkleTree with the following interface:

class RepoMerkleTree:
    def __init__(self, files: dict[str, str]):
        """
        Initializes the Merkle tree from a mapping of relative file paths
        to their string contents.
        Example: {"src/main.py": "print('hello')", "README.md": "# App"}
        """
        pass

    def get_root_hash(self) -> str:
        """
        Returns the hex digest of the root directory hash.
        If the repository is empty, return an empty string "".
        """
        pass

    def diff(self, other: 'RepoMerkleTree') -> dict[str, list[str]]:
        """
        Compares self (base state) against other (target state) and returns
        a dictionary with keys 'added', 'modified', and 'deleted'.
        Each list should contain sorted relative file paths.
        """
        pass

Hashing Specifications

• Use hashlib.sha256(data.encode('utf-8')).hexdigest().
• File hash: sha256(content).
• Directory hash: Sort direct children alphabetically by name. For each child, format an entry as "{name}:{hash}". Join all child entries with "\n", then compute sha256(joined_string). Empty directories do not exist in this representation (directories only exist if they contain files).

Examples

Example 1

tree1 = RepoMerkleTree({
    "src/index.js": "console.log(1);",
    "package.json": "{}"
})
tree2 = RepoMerkleTree({
    "src/index.js": "console.log(2);",
    "src/utils.js": "export const x = 1;",
    "package.json": "{}"
})

print(tree1.diff(tree2))
# Output:
# {
#     "added": ["src/utils.js"],
#     "modified": ["src/index.js"],
#     "deleted": []
# }

Explanation: package.json has the same content and path, so it is skipped. In src/, index.js changed content, and utils.js was newly added.

Constraints

• File paths use forward slashes (/), contain no leading/trailing slashes, and have no redundant segments (. or ..).
• Total number of files per tree <= 10^4.
• Maximum directory depth <= 20.
• When computing diff, do not inspect identical child nodes whose hashes match.