• Or search :

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

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

```def dfs(f, bt)
dfs(f, bt.left) if bt.left
f.(bt)
dfs(f, bt.right) if bt.right
end```
```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) 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)
}
}```
```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
```
```function dfs(bt) {
if (bt === undefined) return;
dfs(bt.left);
f(bt);
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);
}
}```
```void dfs(BinTree bt) {
if (bt.left != null) {
dfs(bt.left);
}
f(bt);
if (bt.right != null) {
dfs(bt.right);
}
}```
```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)```
```(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