read-tree: Walking a Snapshot

The previous lesson built a tree object's hash, but trees in real repositories nest — a directory contains subdirectories which contain more subdirectories. git ls-tree -r (the plumbing command) walks a tree recursively and produces the list of every leaf blob with its full path.

$ git ls-tree -r HEAD
100644 blob b6fc...    README.md
100644 blob 95d0...    src/main.py
100644 blob 5dd0...    src/util/io.py

Notice that ls-tree -r joins the path segments with / — the tree itself stores only the leaf name (io.py), and the parent stores util as a sub-tree entry. The full path is built by the walker.

The recursion

A real implementation also handles:

• Symlinks (mode 120000) — the blob content is the link target.
• Submodules (mode 160000) — the child SHA references a foreign repo; no tree to recurse into.

Why -r matters

Without -r, ls-tree shows only the immediate children. The recursive form is what git diff, git checkout, and git status rely on internally — they compare two flat lists of (path, sha) entries.

That flat list is also the form git read-tree --prefix= writes to the index. The index is essentially "the tree, flattened" — which is why git commit can re-build a tree from the index by reversing the walk.

Performance note

Real git caches the recursion result with a commit-graph + bitmap index, so git ls-tree -r HEAD on the Linux kernel returns in milliseconds despite traversing ~70k entries. The naive walk you'll implement here is O(N) per call — fine for the exercise, but a real implementation re-uses the previously walked trees aggressively.