DROPS

Document

Research

Enumeration of Ordered Trees with Leaf Restrictions

Authors: Yasuaki Kobayashi, Dominik Köppl, Yasuko Matsui, Hirotaka Ono, Toshiki Saitoh, and Yushi Uno

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract

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.

Cite as

Yasuaki Kobayashi, Dominik Köppl, Yasuko Matsui, Hirotaka Ono, Toshiki Saitoh, and Yushi Uno. Enumeration of Ordered Trees with Leaf Restrictions. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:OASIcs.Grossi.8,
  author =	{Kobayashi, Yasuaki and K\"{o}ppl, Dominik and Matsui, Yasuko and Ono, Hirotaka and Saitoh, Toshiki and Uno, Yushi},
  title =	{{Enumeration of Ordered Trees with Leaf Restrictions}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{8:1--8:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.8},
  URN =		{urn:nbn:de:0030-drops-238077},
  doi =		{10.4230/OASIcs.Grossi.8},
  annote =	{Keywords: binary trees, ordered trees, rooted trees, enumeration algorithm, constant-time delay}
}

Search Results

Documents authored by Matsui, Yasuko

Enumeration of Ordered Trees with Leaf Restrictions

Abstract

Cite as

Thanks for your feedback!

Could not send message