Lesson 21 · Diffing two trees - Build a Merkle Tree

Diffing two trees

Comparing two roots tells you something changed; comparing subtree hashes tells you where. Today you diff two trees by walking down only where hashes differ.

The goal

Find which leaf changed by walking the two trees down where subtree hashes differ.

Start here - the target

TO DO

Scenario: Diff locates a single changed leaf

Giventwo trees over ["alice", "bob", "carol", "dave"] and ["alice", "bob", "trent", "dave"]

WhenDiff walks both trees from the root

Thenit reports the changed leaf indices [2]

AndDiff of a tree against an identical tree reports an empty list - equal roots need no walk

Background

If two trees have the same root, they hold identical data - no need to look further. If the roots differ, the change is somewhere below, and the subtree hashes tell you where: descend into a child only when its hash differs between the two trees. Any subtree whose hash matches is provably identical and gets skipped whole. Follow the mismatches down to level 0 and you arrive at exactly the leaves that changed.

This is the git/rsync trick for syncing data cheaply. Rather than compare every item, you compare O(log n) hashes per changed leaf and prune entire unchanged branches at the top. Here, changing carol to trent makes the root differ, then the right subtree differ, then leaf 2 differ - and the walk reports [2]. Two identical trees short-circuit at the root and report nothing.

Make it work

func Diff(a, b *Tree) []int {
  var out []int
  var walk func(level, idx int)
  walk = func(level, idx int) {
    if a.Levels[level][idx] == b.Levels[level][idx] { return } // subtree equal, prune
    if level == 0 { out = append(out, idx); return }
    walk(level-1, 2*idx)
    walk(level-1, 2*idx+1)
  }
  walk(len(a.Levels)-1, 0)
  return out
}

CheckpointDONE

Diff walks down where subtree hashes differ and reports the changed leaf. Commit and stop here.