# Idiom #16 Depth-first traversal of a binary tree

Call a function f on every node of binary tree bt, in depth-first infix order

``````instance Functor BT where
fmap f (BT l x r) = BT (fmap f l) (f x) (fmap f r)

fmap f bt``````
``````inorder Ø = []
inorder (BT left pivot right) =
inorder left ++ pivot : inorder right
f <\$> inorder bt
``````
``````void Dfs(BinaryTree bt)
{
if (bt.Left != null)
Dfs(bt.Left);

f(bt);

if (bt.right != null)
Dfs(bt.Right);
}``````
``````void btTraversal(T)(BinaryTree!T bt, void function(T) f) {
if (bt.left)
btTraversal(*(bt.left), f);

f(bt.data);

if (bt.right)
btTraversal(*(bt.right), f);
}``````
``````traverse(Node bt, f(value)) {
if (bt == null) return;
traverse(bt.left, f);
f(bt.value);
traverse(bt.right, f);
}``````
``````module x
type tree
type (tree), pointer :: left, right
contains
procedure, pass:: trav
end type tree
contains
recursive subroutine trav (t, f)
class (tree), intent(inout) :: t
interface
subroutine f(t)
import
class (tree), intent(inout) :: t
end subroutine f
end interface
if (associated (t%left)) call trav (t%left, f)
call f(t)
if (associated (t%right)) call trav (t%right, f)
end subroutine trav
end module x``````
``````func (bt *BinTree[L]) Dfs(f func(*BinTree[L])) {
if bt == nil {
return
}
bt.Left.Dfs(f)
f(bt)
bt.Right.Dfs(f)
}``````
``````func (bt *BinTree) Dfs(f func(*BinTree)) {
if bt == nil {
return
}
bt.Left.Dfs(f)
f(bt)
bt.Right.Dfs(f)
}``````
``````class BinTree {
BinTree left
BinTree right

void dfs(Closure f) {
left?.dfs(f)
f.call(this)
right?.dfs(f)
}
}``````
``````function dfs(bt) {
if (bt === undefined) return;
dfs(bt.left);
f(bt);
dfs(bt.right);
}``````
``````void dfs(BinTree bt) {
if (bt.left != null) {
dfs(bt.left);
}
f(bt);
if (bt.right != null) {
dfs(bt.right);
}
}``````
``````class BinTree {
// ...

void dfs() {
if( left != null )
left.dfs();
f(this);
if( right != null )
right.dfs();
}
}``````
``import java.util.function.Consumer;``
``````class BinTree<T> {
// ...

void dfs(Consumer<BinTree<T>> f) {
if( left != null )
left.dfs(f);
f.accept(this);
if( right != null )
right.dfs(f);
}
}``````
``````fun dfs(bt: BinaryTree) {
bt.left?.let { dfs(it) }
f(bt)
bt.rigth?.let { dfs(it) }
}``````
``````local function dfs(bt, f, ...)
local tt = type(bt)
if tt~='table' and tt~='userdata' then return end
dfs(t.left, f, ...)
f(t.data, ...)
dfs(t.right, f, ...)
end``````
``````public function dfs(\$f, \$bt)
{
if (\$bt->left != null)
\$this->dfs(\$f, \$bt->left);

\$f(\$bt);

if (\$bt->right != null)
\$this->dfs(\$f, \$bt->right);
}``````
``````sub dfs {
my (\$f, \$bt) = @_;
dfs(\$f, \$bt->{left}) if exists \$bt->{left};
\$f->(\$bt);
dfs(\$f, \$bt->{right}) if exists \$bt->{right};
}``````
``````def dfs(bt):
if bt is None:
return
dfs(bt.left)
f(bt)
dfs(bt.right)``````
``````def dfs(f, bt)
dfs(f, bt.left) if bt.left
f.(bt)
dfs(f, bt.right) if bt.right
end``````
``````struct BiTree<T> {
left: Option<Box<BiTree<T>>>,
right: Option<Box<BiTree<T>>>,
value: T,
}``````
``````fn depthFirstTraverse<T>(bt: &mut BiTree<T>, f: fn(&mut BiTree<T>)) {
if let Some(left) = &mut bt.left {
depthFirstTraverse(left, f);
}

f(bt);

if let Some(right) = &mut bt.right {
depthFirstTraverse(right, f);
}
}``````
``````(define (map-btree f bt)
(if (not (null? bt))
(make-btree (f (btree-value bt))
(map-btree f (btree-left bt))
(map-btree f (btree-right bt)))
bt))``````

programming-idioms.org