Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • 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

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