Idiom # 16: Depth-first traversing of a binary tree

See programming-idioms.org:

Code

traverse (f fun(T)) is match binTree.this nil => n binTreeNode => n.left.traverse f f n.val n.right.traverse f

Running Example

# a binTreeNode is a value plus left and right sub-trees # binTreeNode<T : ordered<T>> (val T, left, right binTree<T>) ref is # add element to this tree, return resulting tree # add (v T) binTree<T> is if (v < val) binTreeNode<T> val, (left.add v), right else if (v > val) binTreeNode<T> val, left , right.add v else binTreeNode<T> v , left , right # a binTree is either a binTreeNode or an empty tree represented by nil # binTree<T : ordered<T>> : choice<binTreeNode<T>, nil> is # add element to this tree, return resulting tree # add (v T) binTree<T> is match binTree.this nil => binTreeNode<T> v, nil, nil n binTreeNode => n.add v # traverse this tree # traverse (f fun(T)) is match binTree.this nil => n binTreeNode => n.left.traverse f f n.val n.right.traverse f animals := ["dog", "elefant", "cat", "cat", "cat", "cat", "lion", "ant", "bee", "albatros", "hyena", "horse", "frog" ] /* NYI: this does not work yet: for tree binTree<string> := nil, tree.add x x in animals else tree.traverse fun (s string) => say s but the following code does: */ tree binTree<string> := nil tree.add("dog") .add("elefant") .add("cat") .add("cat") .add("cat") .add("cat") .add("lion") .add("ant") .add("bee") .add("albatros") .add("hyena") .add("horse") .add("frog") .traverse (fun (s string) => say s)