Merkle tree diff between replicas
Two replicas detect divergence by comparing Merkle trees over their key ranges. Each replica stores a sorted list of leaf hashes (one integer per fixed key bucket; both lists have the same length `m`, which is a power of two). A full binary Merkle tree is built over the leaves bottom-up: a parent hash is `(left * 31 + right) & 0xFFFFFFFF`. To diff, compare roots; if equal, the subtrees match. Otherwise recurse into both children, and at the leaf level record the index of any differing bucket. Return the sorted list of leaf-bucket indices (0-based) where the two replicas differ, visiting only the subtrees whose hashes mismatch (the whole point of the Merkle optimization).
merkle_diff(leaves_a: list[int], leaves_b: list[int]) → list[int][[1,2,3,4],[1,2,9,4]]out[2]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[[1,2,3,4],[1,2,9,4]][2]not run yetsample