Logo

Programming-Idioms

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

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

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