Enumeration, Ranking and Generation of Binary Trees Based on Level-Order Traversal Using Catalan Cipher Vectors

Abstract

In this paper, a new representation of a binary tree is introduced, called the Catalan Cipher Vector, which is a vector of  elements with certain properties. It can be ranked using a special form of the Catalan Triangle designed for this purpose. It is shown that the vector coincides with the level-order traversal of the binary tree and how it can be used to generate a binary tree from it. Streamlined algorithms for directly obtaining the rank from a binary tree and vice versa, using the Catalan Cipher Vector during the processes, are given. The algorithms are analyzed for time and space complexity and shown to be linear for both.
The Catalan Cipher Vector enables a straightforward determination of the position and linking for every node of the binary tree, since it contains information for both every node’s ancestor and the direction of linking from the ancestor to that node. Thus, it is especially well suited for binary tree generation. Using another structure, called a canonical state-space tableau, the relationship between the Catalan Cipher Vector and the level-order traversal of the binary tree is explained.