As someone who just wrote a cargo-tree-alike as well as a fun console screensaver-sort-of-thing, I have some ideas 
The basic idea would be dynamically printing and updating/redrawing the tree based on what's compiling, complete with "throbbers" showing which packages are presently compiling. I've been using crossterm for this, for what it's worth.
A second complication is that any dependency can have multiple "parents" (e.g. many crates use
cc).
cargo-tree (and by extension cargo-audit) solves this by only printing the full dependency subtree for each visited dependency once. This naturally maps to the fact that dependencies only need to be compiled once. So, when you encounter an "already compiled" dependency, perhaps print it for context (or debatably don't), but at that point you're done and don't need to re-display the previously displayed dependency subtree.