Generic traversal of tree structure

Question

I'm trying to write my tree (well, it's binary trie) traversal more generic, because the way it is now I have very similar code repeated.

I'm walking the tree in lexicographical inorder. The example of functions I think can be abstracted by universal tree traversal are (in pseudocode):

items(node*, key, list&) {
    if(node->value)
        list.push({node->value, key})
    if(node->left)
        items(node->value, key + "0")
    if(node->right)
        items(node->value, key + "1")
}

draw(node*, id, ostream&) {
    drawNode(node, id)
    if (node->left)
        drawLine(node, node->left, "0", ostream&)
        draw(node->left, ++id, ostream&)
    if (node->right)
        drawLine(node, node->right, "1", ostream&)
        draw(node->right, ++id, ostream&)

I'm not asking for functioning code, just a push in the right direction. Should it be done with templates taking functions as arguments? What about more complicated cases, where the traversal is not simply conditioned by existence of single left/right node (the merging of two trie seems too like a candidate for this abstraction).

Answer 1

The generic abstraction of traversal is a suitable form of iterator. Once the traversal has become a linear sequence of positions you’d formulate it using one of the conventional iterators, most likely modeling BidirectionalIterator. When generalizing traversal of trees (or more general, graphs) you may have iteration operations moving in different directions.