Idiom #18 Depth-first traversal of a tree

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

``````def dfs(f, node)
f.(node)
node.children.each do |child|
dfs(f, child)
end
end``````
``````void dfs(const auto &tree, const auto &root)
{
f(root);

for (auto child : tree)
dfs(tree, child);
}
``````
``````public static void Dfs(Action<Tree> f, Tree root) {
f(root);
foreach(var child in root.Children)
Dfs(f, child);
} ``````
``````void prefixOrderTraversal(alias f)(ref Tree tree)
{
f(tree);
foreach (child; tree.children)
prefixOrderTraversal!f(child);
}``````
``````traverse(Tree node, f(value)) {
f(node.value);
for (var child in node.children) {
traverse(child, f);
}
}``````
``````  recursive subroutine depth_first (node, f)
type (tr), pointer :: node
interface
subroutine f(node)
import
type(tr), pointer :: node
end subroutine f
end interface
if (associated(node%left)) call depth_first (node, f)
if (associated(node%right)) call depth_first (node, f)
call f(node)
end subroutine depth_first``````
``````func (t *Tree[L]) Dfs(f func(*Tree[L])) {
if t == nil {
return
}
f(t)
for _, child := range t.Children {
child.Dfs(f)
}
}``````
``````func (t *Tree) Dfs(f func(*Tree)) {
if t == nil {
return
}
f(t)
for _, child := range t.Children {
child.Dfs(f)
}
}``````
``````preordered (Node pivot left right) =
pivot : preordered left ++ preordered right
preordered Ø = []
f <\$> (preordered tree)
``````
``````function DFS(f, root) {
f(root)
if (root.children) {
root.children.forEach(child => DFS(f, child))
}
}``````
``````function dfs(\$f, \$root)
{
\$f(\$root);
foreach(\$root as \$child)
{
dfs(\$child);
}
}``````
``````sub depth_first_traversal {
my (\$f, \$treenode) = @_;
\$f->(\$treenode);
depth_first_traversal(\$f, \$_) for @{\$treenode->{children}};
}
``````
``````def DFS(f, root):
f(root)
for child in root:
DFS(f, child)``````
``````pub struct Tree<V> {
children: Vec<Tree<V>>,
value: V
}

impl<V> Tree<V> {
pub fn dfs<F: Fn(&V)>(&self, f: F) {
self.dfs_helper(&f);
}
fn dfs_helper<F: Fn(&V)>(&self, f: &F) {
(f)(&self.value);
for child in &self.children {
child.dfs_helper(f)
}
}
// ...
}``````

programming-idioms.org