Is it possible to traverse a k-ary tree in-order?

Question

According to the Homespring proposed language standard, salmon travelling upstream need to perform "an in-order search of the river system … to find a river node with the same name as the salmon" on the fish tick up (section 6.4.2). The problem is that the river nodes are stored in an n-ary tree, so I'm unsure of how to conduct an in-order search of this tree. A Google search brought up nothing relevant and the Wikipedia page does not even mention any sort of traversal. Is it possible to traverse a k-ary tree in-order?

Answer 1

Yes, it is indeed possible to do this! Let's reason by analogy. In a binary tree, a node looks like this:

            +---+
            | v |
            +---+
           /     \
          T0     T1

An inorder traversal is then done as follows:

1. Recursively do an inorder traversal of T0
2. Visit v
3. Recursively do an inorder traversal of T1.

In other words, you can imagine sweeping from left to right visiting values as you find them. The sweep first hits T0, then hits v, then hits T1.

A node in a multiway tree looks like this:

    +----+----+----+ ... +----+
    | v0 | v1 | v2 | ... | vn |
    +----+----+----+ ... +----+
   /     |    |    |     |     \
  T0    T1    T2   T3   Tn     Tn+1

If we use the "sweep from left to right" idea here, we'd do this:

1. Recursively do an inorder walk of T0.
2. Visit v0.
3. Recursively do an inorder walk of T1.
4. Visit v1.
5. ...
6. Recursively do an inorder walk of Tn.
7. Visit vn.
8. Recursively do an inorder walk of Tn+1.

Here's some pseudocode for this:

void inorderWalk(Node* v) {
    if (v == null) return;

    for (int i = 0; i < v.numChildren; i++) {
        inorderWalk(v.child[i]);
        visit(v.value[i]);
    }
    inorderWalk(v.child[v.numChildren]);
}