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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfæ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-
TidsskriftInformation Processing Letters
Sider (fra-til)32-37
Antal sider6
StatusUdgivet - 2019

ID: 215197420