# Search Results

### Documents authored by Lapey, Paul

Document
##### Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Authors: Paul Lapey and Aaron Williams

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

##### 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.

##### Cite as

Paul Lapey and Aaron Williams. Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

```@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},