Search code examples
prologdcg

Tree postorder traversal in Prolog

Tree traversal refers to the process of visiting each node in a tree data structure in a systematic way. The postorder traversal in the following image

Sorted_binary_tree

returns A, C, E, D, B, H, I, G, F (left, right, root). The Prolog code for PREORDER traversal is

preorder(tree(X,L,R),Xs) :-
    preorder(L,Ls),
    preorder(R,Rs),
    append([X|Ls],Rs,Xs).

preorder(void,[]).

I would like to modify the above code to implement postorder traversal.

Solution

  • In case of a postorder you have to traverse the left branch and get a list of node values Left, then traverse the right branch and get a list of node values Right, and finally return the concatenation of Left, Right and the node value.

    Therefore, to modify your code would be to rearrange the way in which you instantiate the resulting list:

    postorder(tree(X, L, R), Xs):-
  postorder(L, Ls),
  postorder(R, Rs),
  append(Ls, Rs, Xs1),
  append(Xs1, [X], Xs).
postorder(void, []).

    Note however, that this code is suboptimal in the sense that it is not tail recursive. You should consider implementing it with the aid of an accumulator.