The algorithm can't be used - instead one should traverse each commit, see which files were changed, and remove those from the set of all currently tracked files while associating the hash of the commit. Repeat until the set of tracked files is empty.

This will traverse the commit-graph once, in the worst case, and diff the trees of each commit. But there isn't really any other way.