Idiom #128 Breadth-first traversing of a tree

Call a function f on every node of a tree, in breadth-first prefix order

``````def BFS(f, root):
Q = [root]
while Q:
n = Q.pop(0)
f(n)
for child in n:
if not n.discovered:
n.discovered = True
Q.append(n)``````
``````#include <deque>
#include <functional>``````
``````void bfs(Node& root, std::function<void(Node*)> f) {
std::deque<Node*> node_queue;
node_queue.push_back(&root);
while (!node_queue.empty()) {
Node* const node = node_queue.front();
node_queue.pop_front();
f(node);
for (Node* const child : node->children) {
node_queue.push_back(child);
}
}
}``````
``````func (root *Tree) Bfs(f func(*Tree)) {
if root == nil {
return
}
queue := []*Tree{root}
for len(queue) > 0 {
t := queue[0]
queue = queue[1:]
f(t)
queue = append(queue, t.Children...)
}
}``````
``````import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;``````
``````static void breadthFirstSearch(Node root, Consumer<Node> f) {
queue.offer(root);

while(!queue.isEmpty()) {
Node polled = queue.poll();
f.accept(polled);
polled.children.forEach(a -> queue.offer(a));
}
}
``````
``````sub bft {
my (\$f, \$node) = @_;
my @children = \$node->getAllChildren;
return unless @children;
foreach my \$child ( @children ) {
\$f->( \$child->getNodeValue );
}
foreach my \$child ( @children ) {
bft(\$f, \$child);
}
}

my \$f = sub { print \$_[0], "\n" };

# create a tree and populate it, then call bft()
bft(\$f, \$tree);``````
``````class Tree
attr_accessor :value, :children

def initialize(value)
@value = value
@children = []
end

queue = []
queue.unshift(self)
while !(queue.empty?)
node = queue.pop
method(f).call(node.value)
node.children.each { |child| queue.unshift(child) }
end
end
end
``````
``use std::collections::VecDeque;``
``````struct Tree<V> {
children: Vec<Tree<V>>,
value: V
}

impl<V> Tree<V> {
fn bfs(&self, f: impl Fn(&V)) {
let mut q = VecDeque::new();
q.push_back(self);

while let Some(t) = q.pop_front() {
(f)(&t.value);
for child in &t.children {
q.push_back(child);
}
}
}
}``````

programming-idioms.org