2026-09-18T02:36:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23807 2026-09-05T18:31:15Z ddc:004 open_access

Enumeration of Ordered Trees with Leaf Restrictions Kobayashi, Yasuaki Köppl, Dominik Matsui, Yasuko Ono, Hirotaka Saitoh, Toshiki Uno, Yushi binary trees ordered trees rooted trees enumeration algorithm constant-time delay An α-ary tree for a constant α ≥ 2 is a rooted tree in which each node has at most α children. A node having no children is called a leaf. For a given rooted tree and a node v, the number of edges from the root to v is called the depth of v. We call a vector w = (w_1,w_2,…, w_d) of nonnegative integers an (α-ary) distribution if there is an α-ary tree T such that the number of leaves at each depth i ∈ [1..d] in T is w_i. Although not every vector of nonnegative integers is a distribution, a distribution can be associated with many α-ary trees. In this paper, we present an algorithm to enumerate all α-ary trees for a given distribution. Our algorithm reports the first tree in O(d + ∑_{i = 1}^d w_i) time, and then each subsequent α-ary tree in O(max_{i = 1}^d w_i) time by representing each tree as the difference from the previous one. The algorithm can be restricted to computing all trees that are full, i.e., trees whose nodes have exactly α or no children. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yasuaki Kobayashi and Dominik Köppl and Yasuko Matsui and Hirotaka Ono and Toshiki Saitoh and Yushi Uno 2025 Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.8 urn:nbn:de:0030-drops-238077 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.8 eng https://creativecommons.org/licenses/by/4.0/legalcode