Two replicas of the same key range will drift out of sync -- a missed write, a replica that was down for a while, a partial network partition. Reconciling them by comparing every key directly works but doesn't scale: for a large key range, that's a full scan on both sides just to find a handful of differences. Merkle-tree anti-entropy (the mechanism behind Cassandra's and DynamoDB-style stores' read-repair) fixes this: build a tree of hashes over each replica's key range -- leaf hashes over each range's actual data, each internal node the hash of its two children, up to one root hash summarizing the ENTIRE range -- then diff the two replicas' trees top-down. Wherever two nodes' hashes already match, the whole range underneath them is provably identical (the same data hashes to the same hash), so that subtree gets pruned without looking inside it. Only mismatched hashes get followed further down, until landing on the specific leaf ranges that actually differ.

leaf_hashes_for_ranges() and build_merkle_tree() are given. A tree is a list of levels: tree[0] is the leaf level (length = number of ranges, a power of two), tree[-1] is [root_hash]. Level L+1 is built by hashing adjacent pairs from level L, so a node at level L, index i has children at level L-1, indices 2*i and 2*i+1.

Implement diff_ranges(tree_a, tree_b): given two same-shaped trees (same number of levels), return the SORTED list of leaf indices where the two replicas' data actually differs -- found by walking top-down from the root, comparing hashes, and pruning any subtree whose hash matches between the two trees instead of descending into it.

Example

values = ["range-0-data", "range-1-data", "range-2-data", "range-3-data"]
tree_a = build_merkle_tree(leaf_hashes_for_ranges(values))

values[2] = "range-2-DIFFERENT-data"
tree_b = build_merkle_tree(leaf_hashes_for_ranges(values))

diff_ranges(tree_a, tree_b)   # -> [2] -- only the range that actually changed

Constraints

• Only descend into a subtree when its hashes DISAGREE -- a match means the whole subtree is identical and must not be inspected further. This isn't just a style preference: an implementation that just compares every leaf hash directly (ignoring the internal levels) gets the right ANSWER but throws away the entire point of building the tree in the first place, and is checked against directly.
• Return leaf indices, sorted ascending.

Real-world grounding

• Cassandra's Merkle tree: utils/MerkleTree.java -- the leaf-hash/internal-node-hash structure and the top-down difference walk this exercise's diff_ranges implements.
• Cassandra's repair Validator: repair/Validator.java -- builds a MerkleTree from a replica's actual on-disk data during a repair session, the real-world source of the leaf_hashes_for_ranges inputs this exercise takes as given.

Real anti-entropy repair does a lot more on top of this: streaming just the differing ranges' data between replicas (not just identifying them), reconciling per-key timestamps/tombstones once a differing range's actual rows are compared, and running the whole process incrementally so a full repair doesn't need to hold the entire tree in memory at once -- but "diff two hash trees top-down, only pay for what's actually different" is the operation this exercise implements, and it's the same idea every large-scale replicated store uses to make reconciliation affordable.