Breadth-First Traversal

Query 1: What is the breadth-first traversal of the binary tree

       2
     .   .
    1     3

Query 2: What tree(s) 'T' have the breadth-first traversal (a,b,c)?

There are, in general, multiple trees that may have a given breadth-first traversal. Breadth-first traversal, 'bft{.,.)', runs both "forwards" (query 1) and "backwards" (query 2).

Infix Traversal

A program can easily be written to perform infix traversal of a binary tree (here a strict binary tree in which every non-leaf node has exactly two subtrees). However this will not easily run backwards in a Prolog system with only a simple top-down left-to-right evaluation strategy. Either a more complex evaluation strategy is needed or the program must be modified.

Query 1: What is the infix traversal of the tree:

         4
       .   .
     2      5
    . .    . .
   1   3  4   6

Query 2: What tree(s) 'T' have the infix traversal (1,2,3,4,5)?