For twenty-six years, Donald Knuth has given a public lecture in December which he called the “Christmas Tree Lecture”, as he would each time discuss a new result relating to tree data structures and the mathematics of graph theory that underlies them. In recent years, he has broadened the topics beyond trees and renamed the series to just “Christmas Lecture”. For 2022, after a COVID hiatus, he has returned to the roots, as it were, in this lecture which demonstrates how three seemingly entirely different topics:
end up being completely isomorphic to one another, with beautiful algorithms to map one to another in linear time. The programs may be downloaded in the CWEB literate programming system from Dr Knuth’s Web site as:
These topics are discussed in more detail in The Art of Computer Programming, The: Combinatorial Algorithms, Volume 4B, published in October 2022.