breadth first on binary tree - using Semicontext notation

Question

I would like to compute list being bfs order on binary tree. Moreover, it should work in second side - for list it find tree.
Can you give me some hint, so far I have used something like that, of course it doesn't work...

bfs(nil) --> [].
bfs(t(X, L, R)), [X] --> bfs(L), bfs(R).

Answer 1

Looks like @repeat came up with a nice DCG solution. I had, in the meantime, come up with a "traditional" queue-based solution that is non-DCG:

bfs_tree_list(nil, []).
bfs_tree_list(Tree, List) :-
    bfs_q_list([Tree], List).

bfs_q_list([], []).
bfs_q_list([t(X,L,R)|Qs], [X|Xs]) :-
    enqueue(L, Qs, Q1),
    enqueue(R, Q1, Q2),
    bfs_q_list(Q2, Xs).

% "naive" enqueue using append
enqueue(nil, Q, Q).
enqueue(t(X,L,R), Q1, Q2) :- append(Q1, [t(X,L,R)], Q2).

This follows the methodology shown in the links I provided in my comments. It also follows a strict left-to-right traversal ordering which, I believe, is conventional in binary tree traversals. It's a little simpler than those in the links as those are for more general graphs rather than binary trees. The description of what's happening above is simple:

1. Start with the top level in the queue
2. For each element in the queue (until queue is empty)
   (a) Dequeue and accept the current node value
   (b) Enqueue the left and right nodes

The above code yields:

| ?- bfs_tree_list(t(3,t(1,nil,t(2,nil,nil)),t(4,nil,nil)), L).

L = [3,1,4,2]

(1 ms) yes

And:

| ?- bfs_tree_list(Tree, [3,1,4,2]).

Tree = t(3,nil,t(1,nil,t(4,nil,t(2,nil,nil)))) ? a

Tree = t(3,nil,t(1,nil,t(4,t(2,nil,nil),nil)))

Tree = t(3,nil,t(1,t(4,nil,t(2,nil,nil)),nil))

Tree = t(3,nil,t(1,t(4,t(2,nil,nil),nil),nil))

Tree = t(3,nil,t(1,t(4,nil,nil),t(2,nil,nil)))

Tree = t(3,t(1,nil,t(4,nil,t(2,nil,nil))),nil)

Tree = t(3,t(1,nil,t(4,t(2,nil,nil),nil)),nil)

Tree = t(3,t(1,t(4,nil,t(2,nil,nil)),nil),nil)

Tree = t(3,t(1,t(4,t(2,nil,nil),nil),nil),nil)

Tree = t(3,t(1,t(4,nil,nil),t(2,nil,nil)),nil)

Tree = t(3,t(1,nil,nil),t(4,nil,t(2,nil,nil)))

Tree = t(3,t(1,nil,nil),t(4,t(2,nil,nil),nil))

Tree = t(3,t(1,nil,t(2,nil,nil)),t(4,nil,nil))

Tree = t(3,t(1,t(2,nil,nil),nil),t(4,nil,nil))

(1 ms) no
| ?-

---

Here's a revised version that uses a difference list rather than append/3.

bfs_tree_list(nil, []).
bfs_tree_list(Tree, List) :-
    bfs_q_list([Tree|T], T, List).

bfs_q_list(Q, T, []) :- Q == T, !.
bfs_q_list([t(X,L,R)|Qs], T, [X|Xs]) :-
    [t(X,L,R)|Qs] \== T,
    enqueue(L, T1, T),
    enqueue(R, NewT, T1),
    bfs_q_list(Qs, NewT, Xs).

enqueue(nil, Q, Q).
enqueue(t(X,L,R), T, [t(X,L,R)|T]).

Answer 2

This is how you could do it using dcg (without semicontexts) and accumulators:

tree_bfss(T, Xs) :-
   phrase(bfs1([T]), Xs).

bfs1([]) --> [].                    % done if level is empty           
bfs1([X|Xs]) -->
   step_(X, [], Ts),                % single step
   bfs0_(Xs, Ts).                   % process items in this level

bfs0_([], Ts) -->               
   bfs1(Ts).                        % process next level
bfs0_([X|Xs], Ts0) -->
   step_(X, Ts0, Ts),               % single step
   bfs0_(Xs, Ts).                   % continue with this level

step_(nil, Ts, Ts) --> [].
step_(t(L,M,R), Ts, [R,L|Ts]) -->   % push R and L to the next level
   [M].                             % take care of M right now

Sample query using SICStus Prolog 4.3.2:

| ?- tree_bfss(t(t(nil,1,t(nil,2,nil)),3,t(nil,4,nil)), Xs).
Xs = [3,4,1,2] ? ;
no

How about going in the "other" direction?

| ?- tree_bfss(T, [3,4,1,2]).
T = t(t(t(t(nil,2,nil),1,nil),4,nil),3,nil) ? ;
T = t(t(t(nil,1,t(nil,2,nil)),4,nil),3,nil) ? ;
T = t(t(nil,4,t(t(nil,2,nil),1,nil)),3,nil) ? ;
T = t(t(nil,4,t(nil,1,t(nil,2,nil))),3,nil) ? ;
T = t(t(t(nil,2,nil),4,t(nil,1,nil)),3,nil) ? ;
T = t(nil,3,t(t(t(nil,2,nil),1,nil),4,nil)) ? ;
T = t(nil,3,t(t(nil,1,t(nil,2,nil)),4,nil)) ? ;
T = t(nil,3,t(nil,4,t(t(nil,2,nil),1,nil))) ? ;
T = t(nil,3,t(nil,4,t(nil,1,t(nil,2,nil)))) ? ;
T = t(nil,3,t(t(nil,2,nil),4,t(nil,1,nil))) ? ;
T = t(t(nil,1,nil),3,t(t(nil,2,nil),4,nil)) ? ;
T = t(t(nil,1,nil),3,t(nil,4,t(nil,2,nil))) ? ;
T = t(t(t(nil,2,nil),1,nil),3,t(nil,4,nil)) ? ;
T = t(t(nil,1,t(nil,2,nil)),3,t(nil,4,nil)) ? ;
no

Edit

Helpful comments have suggested clarification of the order of the list items:

• Above code does not guarantee any particular order within each single tree level.

• It does ensure that all items of the i^th level occur before all items of the (i+1)^th level.

(This has made the implementation slightly simpler.)