Generation, Ranking and Unranking of Ordered Trees with Degree Bounds

Abstract

We study the problem of generating, ranking and unranking of unlabeled ordered trees whose nodes have maximum degree of Δ. This class of trees represents a generalization of chemical trees. A chemical tree is an unlabeled tree in which no node has degree greater than 4. By allowing up to Δ children for each node of chemical tree instead of 4, we will have a generalization of chemical trees. Here, we introduce a new encoding over an alphabet of size 4 for representing unlabeled ordered trees with maximum degree of Δ. We use this encoding for generating these trees in A-order with constant average time and O(n) worst case time. Due to the given encoding, with a precomputation of size and time O(n^2) (assuming Δ is constant), both ranking and unranking algorithms are also designed taking O(n) and O(nlogn) time complexities.