Hash a Repository with a Merkle Tree and Find Changed Files

Given two directory structures representing consecutive snapshots of a repository, compare them efficiently using a Merkle tree approach. Compute a hash for each node—files and directories—to form a tree. Use these hashes to detect and list all files that have been added, removed, or modified between the two snapshots.

Each file node is represented by its name and content hash. Each directory node is represented by its name and an ordered list of child node hashes. Two snapshots are considered equal at a given node if and only if their hashes match. For directories whose hashes differ, recursively compare their children to identify the specific file-level changes.

Your implementation must handle the following:

• Directory child ordering: sort children by name before hashing to ensure a canonical representation.
• Hash computation: use a consistent hash function (e.g., SHA-256) and a domain separator to avoid collisions between file and directory nodes.
• Change reporting: list changes at the file level only, not at the directory level.

Example 1:

Input:
snapshot_old = {
  "type": "dir",
  "name": "root",
  "children": [
    {
      "type": "dir",
      "name": "src",
      "children": [
        {"type": "file", "name": "main.py", "content_hash": "abc123"}
      ]
    },
    {"type": "file", "name": "README.md", "content_hash": "def456"}
  ]
}
snapshot_new = {
  "type": "dir",
  "name": "root",
  "children": [
    {
      "type": "dir",
      "name": "src",
      "children": [
        {"type": "file", "name": "main.py", "content_hash": "xyz789"}
      ]
    },
    {"type": "file", "name": "README.md", "content_hash": "def456"}
  ]
}

Output: ["src/main.py"]

Explanation: The hash of the src directory changed because main.py's content hash changed. The root hash also changed, but we only report the file-level change.

Example 2:

Input:
snapshot_old = {
  "type": "dir",
  "name": "root",
  "children": [
    {"type": "file", "name": "a.txt", "content_hash": "111"},
    {"type": "file", "name": "b.txt", "content_hash": "222"}
  ]
}
snapshot_new = {
  "type": "dir",
  "name": "root",
  "children": [
    {"type": "file", "name": "a.txt", "content_hash": "111"},
    {"type": "file", "name": "c.txt", "content_hash": "333"}
  ]
}

Output: ["b.txt", "c.txt"]

Explanation: b.txt was removed, and c.txt was added.

Example 3:

Input:
snapshot_old = {
  "type": "dir",
  "name": "root",
  "children": [
    {"type": "file", "name": "log.txt", "content_hash": "aaa"}
  ]
}
snapshot_new = {
  "type": "dir",
  "name": "root",
  "children": [
    {"type": "file", "name": "log.txt", "content_hash": "aaa"}
  ]
}

Output: []

Explanation: The hashes match at every level, so no changes are detected.

Constraints:

• The tree depth does not exceed 50.
• The total number of nodes (files and directories) in each snapshot is between 1 and 10,000.
• File names and directory names consist of lowercase English letters, digits, hyphens, underscores, and dots, with lengths between 1 and 64.
• Content hashes are hexadecimal strings of length 64 (e.g., SHA-256).
• The input snapshots are coherent—no concurrent modifications occur during the comparison process.
• Equality between nodes is determined solely by name and hash; metadata, permissions, and symlink targets are ignored.