Succinct representation of binary trees

In this work, we focus on succinct representation of data structures, especially the representation of binary trees. We show that the number of trees on n nodes is actually the Catalan number, and focus on the level-order representation of binary trees. Three succinct tree representations are explained in detail, and examples are given how to move between them. Not only the space occupancy of the data structure is important, but to support the navigational operations as quickly as possible. For this reason we introduce the RANK and SELECT operations.