## Walkers

In general, iterators over recursive data-structures such as trees are much harder. In particular, if we use either an iterator type or macro, there can be a lot of state that needs to be initialized, maintained and reset. So, it is quite common to see iterators over recursive data-structures to be written as recursive functions.

``````
void
do_something_binary_tree(
binary_tree	tree,
/* other inputs */
)
{
/* do some stuff to tree */
do_something_binary_tree(left_child_binary_tree(tree), /*inputs*/);
do_something_binary_tree(right_child_binary_tree(tree), /*inputs*/);
}
``````

Every time we need to do something different, we need to write a different recursive function.

Instead, we can write walkers. A walker is a function that traverses a recursive data structure in a particular order, and fills in an array with (pointers to) the elements of the data-structure. More concretely:

``````
int
walk_preorder_depth_first_binary_tree(
binary_tree	tree,
int		max,
binary_tree *	array
)
{
int	n;

assert( max > 0 );
array = tree;
n = 1;
n += walk_preorder_depth_first_binary_tree(
left_child_binary_tree, max-n, max+n);
n += walk_preorder_depth_first_binary_tree(
right_child_binary_tree, max-n, max+n);
return n;
}
``````

`walk_preorder_depth_first_binary_tree()` walks a binary tree, filling in the elements of `array` in the same order as the function `do_something_binary_tree()` would process them. Consequently, we can rewrite the function as:

``````
void
do_something_binary_tree(
binary_tree	tree,
/* other inputs */
)
{
int		max = estimate_size_binary_tree(tree);
binary_tree *	temp = xnalloc_stack(binary_tree, max);
int		i;
int		n;
binary_tree	el;

n = walk_preorder_depth_first_binary_tree(tree, max, temp);
for( i = 0; i < n; i++ ) {
el = temp[i];
/* do something to el */
}

xnfree_stack(binary_tree, max, temp);
}
``````

Node: one requirement of using a walker is that we must be able to estimate an upper bound on the maximum number of nodes in the data-structure to be traversed. The walker will return the actual number of nodes in the data-structure.

Now, any other function that must traverse `binary_tree` in pre depth first order can be written as a combination of the walker and then a simple `for` loop over the array returned by the walker.

Next Prev Main Top Feedback