Logo

Programming-Idioms

  • Java
  • Python
  • Go
  • Rust

Idiom #16 Depth-first traversal of a binary tree

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

void dfs(BinTree bt) {
	if (bt.left != null) {
		dfs(bt.left);
        }
	f(bt);
	if (bt.right != null) {
		dfs(bt.right);
        }
}

Here, the call to f is hard-coded, we can't specify f as a parameter.
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);
	}
}

This works in java >= 8.

dfs is a method.

f is functional argument.
class BinTree {
	// ...

	void dfs() {
		if( left != null )
			left.dfs();
		f(this);
		if( right != null )
			right.dfs();
	}
}

dfs is a method.

Here, the call to f is hard-coded, we can't specify f as a parameter.
def dfs(bt):
	if bt is None:
		return
	dfs(bt.left)
	f(bt)
	dfs(bt.right)

Recursive DFS.
func (bt *BinTree[L]) Dfs(f func(*BinTree[L])) {
	if bt == nil {
		return
	}
	bt.Left.Dfs(f)
	f(bt)
	bt.Right.Dfs(f)
}

The type parameter L is for arbitrary node label data
func (bt *BinTree) Dfs(f func(*BinTree)) {
	if bt == nil {
		return
	}
	bt.Left.Dfs(f)
	f(bt)
	bt.Right.Dfs(f)
}

The function f is a parameter of the traversal method Dfs.
It's legit to call a method on a nil receiver, and useful to make code more concise with less checks for nil.
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);
    }
}
void Dfs(BinaryTree bt)
{
    if (bt.Left != null) 
        Dfs(bt.Left);

    f(bt);

    if (bt.right != null) 
        Dfs(bt.Right);
}
New implementation...
< > ⌨
programming-idioms.org 
void dfs(BinTree bt) {
	if (bt.left != null) {
		dfs(bt.left);
        }
	f(bt);
	if (bt.right != null) {
		dfs(bt.right);
        }
}
class BinTree<T> {
	// ...

	void dfs(Consumer<BinTree<T>> f) {
		if( left != null )
			left.dfs(f);
		f.accept(this);
		if( right != null )
			right.dfs(f);
	}
}
class BinTree {
	// ...

	void dfs() {
		if( left != null )
			left.dfs();
		f(this);
		if( right != null )
			right.dfs();
	}
}
def dfs(bt):
	if bt is None:
		return
	dfs(bt.left)
	f(bt)
	dfs(bt.right)
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)
}
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);
    }
}
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
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);
}
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(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))