Logo

Programming-Idioms

  • Ruby
  • C++
  • Haskell
  • C#
  • JS
  • Java
  • Go
  • Python

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, 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
void dfs(const auto &tree, const auto &root)
{
	f(root);

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

preordered (Node pivot left right) = 
   pivot : preordered left ++ preordered right
preordered Ø = []
f <$> (preordered tree)

public static void Dfs(Action<Tree> f, Tree root) {
    f(root);
    foreach(var child in root.Children)
        Dfs(f, child);
} 
function DFS(f, root) {
	f(root)
	if (root.children) {
		root.children.forEach(child => DFS(f, child))
	}
}

Works in ES6
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 prefixOrderTraversal(alias f)(ref Tree tree)
{
	f(tree);
	foreach (child; tree.children)
		prefixOrderTraversal!f(child);
}

This version takes f as a compile-time parameter, allowing inlining and other optimizations.
New implementation...
< > ⌨
programming-idioms.org 
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
void dfs(const auto &tree, const auto &root)
{
	f(root);

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

preordered (Node pivot left right) = 
   pivot : preordered left ++ preordered right
preordered Ø = []
f <$> (preordered tree)

public static void Dfs(Action<Tree> f, Tree root) {
    f(root);
    foreach(var child in root.Children)
        Dfs(f, child);
} 
function DFS(f, root) {
	f(root)
	if (root.children) {
		root.children.forEach(child => DFS(f, child))
	}
}
func (t *Tree[L]) Dfs(f func(*Tree[L])) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}
func (t *Tree) Dfs(f func(*Tree)) {
	if t == nil {
		return
	}
	f(t)
	for _, child := range t.Children {
		child.Dfs(f)
	}
}
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
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}};
}

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)
        }
    }
    // ...
}