A) I've seen this before but I've never thought of the "index as a bit-sequence describing when in the tree a left vs. right path was taken" before! This is a very nice intuitive explanation that'll really help in describing this to others.

B) Did you mean Floyd-Warshall's?