# Tree Breadth-First in Prolog

**URL:** <https://swi-prolog.discourse.group/t/tree-breadth-first-in-prolog/1541>\
**Category:** Help!\
**Created:** [November 26, 2019, 7:39pm UTC](https://swi-prolog.discourse.group/t/tree-breadth-first-in-prolog/1541 "2019-11-26T19:39:09Z")\
**Posts on this page:** 1\
**Showing post:** 18

<div class="post-metadata">

**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\
**Post date:** [November 28, 2019, 8:42am UTC](https://swi-prolog.discourse.group/t/tree-breadth-first-in-prolog/1541/18 "2019-11-28T08:42:21Z")

</div>

Here’s a slightly more polished version with no cuts or carets, and also returns the traversal path as a list (which is typically what you want). It doesn’t avoid cycles, but checking to see if a node has already been visited wouldn’t require much more work.

```prolog
:- op(500,xfx,'is_parent').

a is_parent b. c is_parent g. f is_parent l. j is_parent q.
a is_parent c. c is_parent h. f is_parent m. j is_parent r.
a is_parent d. c is_parent i. h is_parent n. j is_parent s.
b is_parent e. d is_parent j. i is_parent o. m is_parent t.
b is_parent f. e is_parent k. i is_parent p.

getchildren(Parent, Children) :-
    findall(Child, Parent is_parent Child, Unsorted),
    sort(Unsorted, Children).

depthfirst([], []).
depthfirst([Node|Frontier], [Node|Visited]) :-
    getchildren(Node, Children),
    append(Children, Frontier, NewFrontier),
    depthfirst(NewFrontier, Visited).

breadthfirst([], []).
breadthfirst([Node|Frontier], [Node|Visited]) :-
    getchildren(Node, Children),
    append(Frontier, Children, NewFrontier),
    breadthfirst(NewFrontier, Visited).

```

```prolog
?- depthfirst([a], Path), print(Path).
[a,b,e,k,f,l,m,t,c,g,h,n,i,o,p,d,j,q,r,s]
Path = [a, b, e, k, f, l, m, t, c|...].

?- breadthfirst([a], Path), print(Path).
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t]
Path = [a, b, c, d, e, f, g, h, i|...].

```

---

_[View the full topic](https://swi-prolog.discourse.group/t/tree-breadth-first-in-prolog/1541)._