The declarative programming language Prolog is very suitable for reasoning about trees, lists and recursive structures in general. For example, here is a Prolo

The declarative programming language Prolog is very suitable for reasoning about trees, lists and recursive structures in general. For example, here is a Prolog definition of the tree from the article: tree(node(4, node(2, node(1,nil,nil), node(3,nil,nil)), node(5,nil,nil))). I am using terms of the form nil/0 and node/3 to represent the tree. Let us start by converting the tree to a list. As requested, we shall consider the in-order traversal of the tree elements, described as a list. For such situations, Prolog DCG notation is very convenient, since it easily allows us to describe a list in relation to other terms (in this case, a tree): tree_to_list(nil) --> []. tree_to_list(node(E,Left,Right)) --> tree_to_list(Left), [E], tree_to_list(Right). Here is a sample query and its result: ?- tree(T), phrase(tree_to_list(T), Ls). T = node(4, ...), Ls = [1, 2, 3, 4, 5]. OK, so we now have the in-order traversal. Of course, lists are already implicitly "linked" in Prolog in one direction: Given a list, we can readily reason about the first element and the remaining elements. The task requires us to do more, i.e., reason about the reverse direction as well. One way to express this is to use rational trees, also known as cyclic terms in Prolog. For example, here is a case of cyclic term: ?- append([a,b,c], Ls, Ls). Ls = [a, b, c|Ls]. Here, Ls represents the circular list [a,b,c,a,b,c,a,...]. We can use this feature to our advantage as follows: list_with_backlinks([], []). list_with_backlinks([L|Ls0], [L-Prev|Ls]) :- append([L|Ls], Cs, Cs), foldl(with_backlink, Ls0, Ls, Cs, Prev). with_backlink(E, E-Cs0, Cs0, Cs) :- Cs0 = [_|Cs]. Sample query and answer: ?- list_with_backlinks([a,b,c], Cs). Cs = [a-[_S2|_S1], b-_S1, _S2], % where _S1 = [a, b-_S1, _S2|_S1], _S2 = c-[b-_S1, _S2|_S1] . Thus, as desired, we can generate a doubly-linked list from the original tree: ?- tree(T), phrase(tree_to_list(T), Ls0), list_with_backlinks(Ls0, Ls). T = node(4, ...), Ls0 = [1, 2, 3, 4, 5], Ls = [1-[_S4|_S1], 2-_S1, _S2, _S3, _S4], % where _S1 = [1, 2-_S1, _S2, _S3, _S4|_S1], _S2 = 3-[2-_S1, _S2, _S3, _S4|_S1], _S3 = 4-[_S2, _S3, _S4|_S1], _S4 = 5-[_S3, _S4|_S1] . Of course, this does not completely solve the task, which requires in-place modifications of the original tree. Pure Prolog lacks destructive modifications, so we cannot fully translate the code to Prolog. On the plus side, no pointers at all were necessary, and the recursions are pretty straight-forward.