4.9.3 Better Iterative Traversal |

We have developed an efficient, convenient function for traversing a binary tree. In the exercises, we made it reliable, and it is possible to make it resilient as well. But its algorithm makes it difficult to add generality. In order to do that in a practical way, we will have to use a new algorithm.

Let us start by considering how to understand how to find the successor
or predecessor of any node in general, as opposed to just blindly
transforming code as we did in the previous section. Back when we wrote
*bst_delete*(), we already solved half of the problem, by figuring out
how to find the successor of a node that has a right child: take the
least-valued node in the right subtree of the node (see Deletion Case 3).

The other half is the successor of a node that doesn't have a right child. Take a look at the code for one of the previous traversal functions—recursive or iterative, whichever you better understand—and mentally work out the relationship between the current node and its successor for a node without a right child. What happens is that we move up the tree, from a node to its parent, one node at a time, until it turns out that we moved up to the right (as opposed to up to the left) and that is the successor node. Think of it this way: if we move up to the left, then the node we started at has a lesser value than where we ended up, so we've already visited it, but if we move up to the right, then we're moving to a node with a greater value, so we've found the successor.

Using these instructions, we can find the predecessor of a node, too,
just by exchanging “left” and “right”. This suggests that all we
have to do in order to generalize our traversal function is to keep
track of all the nodes above the current node, not just the ones that
are up and to the left. This in turn suggests our final implementation
of **struct** **bst_traverser**, with appropriate comments:

62. <BST traverser structure 62> = /* BST traverser structure. */structbst_traverser

{structbst_table*bst_table; /* Tree being traversed. */structbst_node*bst_node; /* Current node in tree. */structbst_node*bst_stack[BST_MAX_HEIGHT];

/* All the nodes abovebst_node. */size_tbst_height; /* Number of nodes inbst_parent. */unsignedlongbst_generation; /* Generation number. */ };

This code is included in 25, 143, and 194.

Because user code is expected to declare actual instances of **struct** **bst_traverser**, **struct** **bst_traverser** must be defined in <`bst.h` 25> and
therefore all of its member names are prefixed by *bst_* for safety.

The only surprise in **struct** **bst_traverser** is member *bst_generation*,
the traverser's generation number. This member is set equal to its
namesake in **struct** **bst_table** when a traverser is initialized. After
that, the two values are compared whenever the stack of parent pointers
must be accessed. Any change in the tree that could disturb the action
of a traverser will cause their generation numbers to differ, which in
turn triggers an update to the stack. This is what allows this final
implementation to be resilient.

We need a utility function to actually update the stack of parent pointers when differing generation numbers are detected. This is easy to write:

63. <BST traverser refresher 63> = /* Refreshes the stack of parent pointers intravand updates its generation number. */staticvoidtrav_refresh(structbst_traverser*trav)

{assert(trav!=NULL);trav->bst_generation=trav->bst_table->bst_generation;if(trav->bst_node!=NULL)

{bst_comparison_func*cmp=trav->bst_table->bst_compare;void*param=trav->bst_table->bst_param;structbst_node*node=trav->bst_node;structbst_node*i;trav->bst_height= 0;for(i=trav->bst_table->bst_root;i!=node; )

{assert(trav->bst_height<BST_MAX_HEIGHT);assert(i!=NULL);trav->bst_stack[trav->bst_height++] =i;i=i->bst_link[cmp(node->bst_data,i->bst_data,param) > 0]; } } }

This code is included in 64 and 180.

The following sections will implement all of the traverser functions
*bst_t_**(). See Traversers, for descriptions of the purpose of each
of these functions.

The traversal functions are collected together into <BST traversal functions 64>:

64. <BST traversal functions 64> = <BST traverser refresher 63> <BST traverser null initializer 65> <BST traverser least-item initializer 66> <BST traverser greatest-item initializer 67> <BST traverser search initializer 68> <BST traverser insertion initializer 69> <BST traverser copy initializer 70> <BST traverser advance function 71> <BST traverser back up function 74> <BST traverser current item function 75> <BST traverser replacement function 76>

This code is included in 30.

**Exercises:**

**1.** The *bst_probe*() function doesn't change the tree's generation number.
Why not?
[answer]

***2.** The main loop in *trav_refresh*() contains the assertion

assert(trav->bst_height<BST_MAX_HEIGHT);

Prove that this assertion is always true. [answer]

**3.** In *trav_refresh*(), it is tempting to avoid calls to the user-supplied
comparison function by comparing the nodes on the stack to the current
state of the tree; e.g., move up the stack, starting from the bottom,
and for each node verify that it is a child of the previous one on the
stack, falling back to the general algorithm at the first mismatch. Why
won't this work?
[answer]