Logo

Programming-Idioms

  • Python
  • Java
  • Erlang
  • Dart

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
traverse(Tree node, f(value)) {
  f(node.value);
  for (var child in node.children) { 
    traverse(child, f);
  }
}
def DFS(f, root):
	f(root)
	for child in root:
		DFS(f, child)
void dfs(const auto &tree, const auto &root)
{
	f(root);

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

New implementation...