We are dealing with a Most similar neighbour algorithm here. Part of the algorithm involves searching in order over a tree.
The thing is that until now, we can't make that tree to be binary.
Is there an analog to in order traversal for non-binary trees. Particularly, I think there is, just traversing the nodes from left to right (and processing the parent node only once?")
This tree will have in each node a small graph of n objects. Each node will have n children (1 per each element in the graph), each of which will be another graph. So its "kind of" a b tree, without all the overflow - underflow mechanics. So I guess the most similar in order traversal would be similar to a btree inorder traversal ?
Yes, but you need to define what the order is. Post and Pre order are identical, but inorder takes a definition of how the branches compare with the nodes.