This language bar is your friend. Select your favorite languages!

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

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)
}
inorder Ø = []
inorder (BT left pivot right) =
  inorder left ++ pivot : inorder right
f <$> inorder bt
instance Functor BT where
  fmap f (BT l x r) = BT (fmap f l) (f x) (fmap f r)

fmap f bt
function dfs(bt) {
	if (bt === undefined) return;
	dfs(bt.left);
	f(bt);
	dfs(bt.right);
}
class BinTree {
	// ...

	void dfs() {
		if( left != nil )
			left.dfs();
		f(this);
		if( right != nil )
			right.dfs();
	}
}
void dfs(BinTree bt) {
	if( bt.left != nil )
		dfs(bt.left);
	f(bt);
	if( bt.right != nil )
		dfs(bt.right);
}
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);
	}
}
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
(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))

Do you know the best way to do this in your language ?
New implementation...

Idiom created by

programming-idioms.org

Related idioms