Implement a Merkle-tree repo diff

You are given two snapshots of a source-code repository on disk, each represented by a root directory path. Implement a Merkle tree over the directory structure (folders are internal nodes, files are leaves), and use it to compute which files changed between the two snapshots.

Use the following API (Python-like):

from enum import Enum, auto
from typing import Self

class ChangeType(Enum):
    ADDED = auto()
    MODIFIED = auto()
    REMOVED = auto()

class MerkleTree:
    def __init__(self, root_directory: str):
        """Build the Merkle tree from the filesystem under root_directory."""
        ...

    def diff(self, other: Self) -> list[tuple[str, ChangeType]]:
        """Return a list of (relative_path, ChangeType) for all files that differ."""
        ...

Requirements / clarifications:

• The tree structure must follow the actual folder hierarchy in the repo (not a binary tree).
• A file node’s hash should depend on its contents (and optionally its name); a directory node’s hash should depend on its children (names + hashes) in a deterministic order.
• diff() should report files only as:
  • ADDED: path exists only in other.
  • REMOVED: path exists only in self.
  • MODIFIED: path exists in both but file contents differ.
• Paths in the output should be relative to the root (e.g., "src/main.py").
• If a path changes type (file ↔ directory), you may treat it as removed + added for the affected file paths.
• Use only the standard library to read directories/files.

Design and implement the data structures and logic so it can run against real repositories on disk.

Implement a Merkle-Tree Repo Diff

Implement a repository diff using a Merkle tree that mirrors the real directory hierarchy. Files are leaves, and directories are internal nodes with any number of children. A file node's hash must depend on its contents. A directory node's hash must depend on its children's names, types, and hashes in a deterministic sorted order. If two directory hashes are equal, you should be able to skip that entire subtree during diffing.

Original interview API:

• MerkleTree(root_directory)
• diff(other) -> list[(relative_path, ChangeType)]

To keep the judge self-contained, implement solution(snapshot_a, snapshot_b) instead. Each snapshot is a list of (relative_path, contents) pairs describing the files in that repository snapshot. Paths use / as the separator, and directories are implied by the file paths.

Your implementation should still follow the real on-disk logic from the interview question. The reference solution materializes the snapshots into temporary directories, builds an on-disk Merkle tree using only the standard library, and diffs the two trees.

Return a lexicographically sorted list of (relative_path, change_type) for files only, where change_type is one of 'ADDED', 'MODIFIED', or 'REMOVED'.

• ADDED: path exists only in snapshot_b
• REMOVED: path exists only in snapshot_a
• MODIFIED: path exists in both snapshots but file contents differ

If a path changes type between snapshots (file <-> directory), treat it as removed plus added for the affected file paths.

Constraints

• 0 <= len(snapshot_a), len(snapshot_b) <= 2000
• The total size of all file contents across both snapshots is at most 2 * 10^6 bytes
• Within a single snapshot, all relative paths are unique
• Within a single snapshot, no file path is a prefix of another file path
• Paths are relative, use '/' as the separator, and refer only to regular files and directories implied by those paths

Examples

Example 1

Input: ([('README.md', 'repo'), ('src/main.py', 'main\n'), ('src/util.py', 'add\n')], [('README.md', 'repo'), ('src/main.py', 'main\n'), ('src/util.py', 'add\n')])
Output: []

Explanation: Both snapshots contain the same files with the same contents, so no file differs.

Example 2

Input: ([('README.md', 'repo'), ('src/main.py', 'v1\n'), ('src/utils/helpers.py', 'helper\n'), ('docs/old.md', 'old\n')], [('README.md', 'repo'), ('src/main.py', 'v2\n'), ('src/utils/helpers.py', 'helper\n'), ('src/utils/new.py', 'new\n'), ('tests/test_main.py', 'ok\n')])
Output: [('docs/old.md', 'REMOVED'), ('src/main.py', 'MODIFIED'), ('src/utils/new.py', 'ADDED'), ('tests/test_main.py', 'ADDED')]

Explanation: One file was removed, one existing file changed contents, and two new files were added.

Hints

1. Hash each file from its contents, and hash each directory from its sorted children as tuples like (name, kind, child_hash). Deterministic ordering is essential.
2. When diffing, if two directory hashes are equal, you can skip the whole subtree. Only recurse when hashes differ or when a child exists on just one side.

Approach

Idea. Both snapshots are turned into in-memory Merkle trees that mirror the directory hierarchy (files = leaves, directories = internal nodes). Equal subtree hashes let the diff skip whole subtrees, so unchanged folders cost nothing.

Building the tree (build_tree). Each (path, contents) pair is split on /; intermediate components become dir nodes and the last becomes a file node. A file's hash is sha256(b'FILE|' + bytes(contents)) (file_hash), so it depends only on contents. compute_dir_hashes then post-orders the tree with an explicit two-phase stack (state 0 = push children, state 1 = combine). A directory's hash folds in each child's type byte (F/D), name, and child hash, iterating sorted(node.children.keys()) with \x00 separators — making the hash deterministic and order-independent.

Diffing (diff_trees). Starting from both roots, it walks paired directories on a stack. If a.hash == b.hash the subtree is identical and skipped. Otherwise it unions child names and, per name:

• present only in B → every file under it is ADDED (collect_files_changes);
• only in A → REMOVED;
• file/file → MODIFIED iff hashes differ;
• dir/dir → recurse only when hashes differ;
• file↔dir type change → the file side is REMOVED/ADDED and the other side's files are emitted accordingly.

Results are finally sort()ed lexicographically. This is correct because file hashes capture content and directory hashes capture the full sorted child structure, so hash equality is a sound certificate that a subtree is unchanged.

• Time complexity: O(S + N log N)
• Space complexity: O(N)