Constructing a binary tree from its traversals by reversible recursion and iteration

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfællebedømt

We cast two algorithms to generate the inorder and preorder of the labels of a binary tree in the context of reversible computing nearly three decades after they were first examined in the light of program inversion. The reversible traversals directly define the inverse algorithms that reconstruct the binary tree and have the same linear time and space requirements as the traversals. A reversible while-language is extended with reversible recursion-
OriginalsprogEngelsk
TidsskriftInformation Processing Letters
Vol/bind147
Sider (fra-til)32-37
Antal sider6
ISSN0020-0190
DOI
StatusUdgivet - 2019

ID: 215197420