Logo

Programming-Idioms

  • JS
  • Elixir
  • Java
  • Ruby

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
def dfs(f, node)
  f.(node)
  node.children.each do |child|
    dfs(f, child)
  end
end
function DFS(f, root) {
	f(root)
	if (root.children) {
		root.children.forEach(child => DFS(f, child))
	}
}

Works in ES6
void dfs(const auto &tree, const auto &root)
{
	f(root);

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

New implementation...