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

Idiom

# 16 Depth-first traversal 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[L]) Dfs(f func(*BinTree[L])) {
	if bt == nil {
		return
	}
	bt.Left.Dfs(f)
	f(bt)
	bt.Right.Dfs(f)
}

Demo

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

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

Demo
Doc

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

Preview