Logo

Programming-Idioms

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

Implementation edit is for fixing errors and enhancing with metadata. Please do not replace the code below with a different implementation.

Instead of changing the code of the snippet, consider creating another Python implementation.

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations
func (t *Tree) Dfs(f func(*Tree)) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}
sub depth_first_traversal {
   my ($f, $treenode) = @_;
   $f->($treenode);
   depth_first_traversal($f, $_) for @{$treenode->{children}};
}
void prefixOrderTraversal(alias f)(ref Tree tree)
{
	f(tree);
	foreach (child; tree.children)
		prefixOrderTraversal!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)
        }
    }
    // ...
}
traverse(Tree node, f(value)) {
  f(node.value);
  for (var child in node.children) { 
    traverse(child, f);
  }
}
def dfs(f, node)
  f.(node)
  node.children.each do |child|
    dfs(f, child)
  end
end
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);
    }	
}
void dfs(const auto &tree, const auto &root)
{
	f(root);

	for (auto child : tree)
		dfs(tree, child);
}
  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
public static void Dfs(Action<Tree> f, Tree root) {
    f(root);
    foreach(var child in root.Children)
        Dfs(f, child);
} 
func (t *Tree[L]) Dfs(f func(*Tree[L])) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}