Logo

Programming-Idioms

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

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations
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)
    }
}
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);
}
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))