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

Research output: Contribution to journalJournal articleResearchpeer-review

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-
Original languageEnglish
JournalInformation Processing Letters
Pages (from-to)32-37
Number of pages6
Publication statusPublished - 2019

ID: 215197420