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

TY - JOUR

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

AU - Glück, Robert

AU - Yokoyama, Tetsuo

PY - 2019/7

Y1 - 2019/7

N2 - 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-

AB - 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-

U2 - 10.1016/j.ipl.2019.03.002

DO - 10.1016/j.ipl.2019.03.002

M3 - Journal article

SN - 0020-0190

VL - 147

SP - 32

EP - 37

JO - Information Processing Letters

JF - Information Processing Letters

ER -