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[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.