Creating implementation for idiom 16 : Depth-first traversing of a binary tree

Idiom

# 16 Depth-first traversing of a binary tree

Created by

Lead paragraph

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

New implementation

Language

Imports

Code

Documentation URL

Original attribution URL

Online runnable demo

Username

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) Dfs(f func(*BinTree)) {
	if bt == nil {
		return
	}
	bt.Left.Dfs(f)
	f(bt)
	bt.Right.Dfs(f)
}

Demo

class BinTree {
    BinTree left
    BinTree right

    void dfs(Closure f) {
        left?.dfs(f)
        f.call(this)
        right?.dfs(f)
    }
}

Demo

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 != 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);
	}
}

Demo
Doc

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)

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))

Preview