Whereas inorder traversal of an *N*-ary tree is *not* defined for *N**>*2,
inorder traversal *is* defined for an *M*-way search tree:
By definition, the inorder traversal of a search tree visits
all the keys contained in the search tree *in order*.

Program is an implementation of
the algorithm for depth-first traversal of an *M*-way search tree
given in Section .
The keys contained in a given node are visited
(by calling the `Visit` member function of the visitor)
*in between* the appropriate subtrees of that node.
In addition,
the `PreVisit` function is called for each key contained in a node
before traversing any of the subtrees of that node
and the `PostVisit` function is called for each key
in the node after all the subtrees have been traversed.

**Program:** `MWayTree` Class `DepthFirstTraversal` Member Function Definition

It is clear that the amount of work done at each node
during the course of a depth-first traversal
is proportional to the number of keys contained in that node.
Therefore, the total running time for the depth-first traversal is
,
where *K* is the number of keys contained in the search tree.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.