Logo

Programming-Idioms

# 18 Depth-first traversal of a tree
Call a function f on every node of a tree, in depth-first prefix order
New 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 
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) Dfs(f func(*Tree)) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}
func (t *Tree[L]) Dfs(f func(*Tree[L])) {
	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)
def dfs(f, node)
  f.(node)
  node.children.each do |child|
    dfs(f, child)
  end
end
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)
        }
    }
    // ...
}

Preview