Logo

Programming-Idioms

  • C#
  • Php

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
function dfs($f, $root)
{
    $f($root);
    foreach($root as $child)
    {
        dfs($child);
    }	
}

Here dfs is a recursive function to traverse the tree applying a function sent as the $f parameter
public static void Dfs(Action<Tree> f, Tree root) {
    f(root);
    foreach(var child in root.Children)
        Dfs(f, child);
} 
void dfs(const auto &tree, const auto &root)
{
	f(root);

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

New implementation...