example(0, tree(a, [tree(b, [tree(c, []), tree(d, [])]), tree(e, [tree(f,[])])])).

dfs(T, L) :- dfsD(0, T, L).

dfsD(D, tree(V, Ts), [(D, V) | L]) :-
    D1 is D + 1,
    maplist(dfsD(D1), Ts, Ls),
    append(Ls, L).

dfsF(tree(V, Ts), L) :-
    dfsF([(0, tree(V, Ts))], L).


dfsF([],[]).
dfsF([(D, tree(V, Ts)) | T], [(D, V) | L]) :-
    D1 is D + 1,
    findall((D1, X), member(X, Ts), Fs),
    append(Fs, T, T1),
    dfsF(T1, L).
    
bfsF(tree(V, Ts), L) :-
    bfsF([(0, tree(V, Ts))], L).

bfsF([], []).
bfsF([(D, tree(V, Ts)) | T], [(D, V) | L]) :-
    D1 is D + 1,
    findall((D1, X), member(X, Ts), Fs),
    append(T, Fs, T1),
    bfsF(T1, L).

itd(T, L) :-
    itd(1, T, L), !.

itd(C, T, L) :-
    dfsUpTo(0, C, T, L, done).

itd(C, T, L) :-
    dfsUpTo(0, C, T, L1, go),
    C1 is C + 1,
    itd(C1, T, L2),
    append(L1, L2, L).

dfsUpTo(D, C, _, [], go) :-
    D > C, !.

dfsUpTo(D, C, tree(V, Ts), [(D, V) | L], Done) :-
    D1 is D + 1,
    maplist(dfsUpTo(D1, C), Ts, Ls, Ds),
    append(Ls, L),
    done(Done, Ds).

done(done, []).
done(go , [go | _]).
done(Done, [done | Ds]) :-
    done(Done, Ds).