Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Go

Idiom #18 Depth-first traversal of a tree

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

A tree having 6 nodes, rooted at node 1
func (t *Tree[L]) Dfs(f func(*Tree[L])) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}

The type parameter L is for arbitrary node label data
func (t *Tree) Dfs(f func(*Tree)) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}

The function f is a parameter of the traversal method Dfs .
The traversal is prefix because f is applied to current node first.
void dfs(const auto &tree, const auto &root)
{
	f(root);

	for (auto child : tree)
		dfs(tree, child);
}

New implementation...