When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.53
URN: urn:nbn:de:0030-drops-173380
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17338/
 Go to the corresponding LIPIcs Volume Portal

Pop & Push: Ordered Tree Iteration in š¯’Ŗ(1)-Time

 pdf-format:

Abstract

The number of ordered trees (also known as plane trees) with n nodes is the (n-1)st Catalan number C_{n-1}. An ordered tree can be stored directly using nodes and pointers, or represented indirectly by a Dyck word. This paper presents a loopless algorithm for generating ordered trees with n nodes using pointer-based representations. In other words, we spend š¯’Ŗ(C_{n-1})-time to generate all of the trees, and moreover, the delay between consecutive trees is worst-case š¯’Ŗ(1)-time.
To achieve this run-time, each tree must differ from the previous by a constant amount. In other words, the algorithm must create a type of Gray code order. Our algorithm operates on the children of a node like a stack, by popping the first child off of one nodeā€™s stack and pushing the result onto another nodeā€™s stack. We refer to this pop-push operation as a pull, and consecutive trees in our order differ by one or two pulls. There is a simple two-case successor rule that determines the pulls to apply directly from the current tree. When converted to Dyck words, our rule corresponds to a left-shift, and these shift generate a cool-lex variant of lexicographic order.
Our results represent the first pull Gray code for ordered trees, and the first fully published loopless algorithm for ordered trees using pointer representations. More importantly, our algorithm is incredibly simple: A full implementation in C, including initialization and output, uses only three loops and three if-else blocks. Our work also establishes a simultaneous Gray code for Dyck words, ordered trees, and also binary trees, using cool-lex order.

BibTeX - Entry

```@InProceedings{lapey_et_al:LIPIcs.ISAAC.2022.53,
author =	{Lapey, Paul and Williams, Aaron},
title =	{{Pop \& Push: Ordered Tree Iteration in š¯’Ŗ(1)-Time}},
booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages =	{53:1--53:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-258-7},
ISSN =	{1868-8969},
year =	{2022},
volume =	{248},
editor =	{Bae, Sang Won and Park, Heejin},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},