As he says in the first 30 seconds of the video, the lecture has been called the "Annual Christmas Tree Lecture" for 20 years, and it was always a lecture about trees in computer science as a bit of a pun. Dr. Knuth said - again, right at the start - that he had trouble finding a good tree-related subject, so he dropped "tree" from the name.