Perform a depth-first search on the tree, starting from the root.

During the DFS, keep track of the most recent node where each character from 'a' to 'z' has been seen.