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[0] = 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