4

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees)

  1. Perform pre-order operation
  2. For each i (with i = 1 to n) do:
    1. Visit i-th, if present
    2. Perform in-order operation
  3. Perform post-order operation

where n is the number of child nodes.

The pre-order and post-order parts make sense. The in-order one does not make sense to me however. By performing this algorithm I would perform the in-order operation on the same node several times. Basically, if I have a node with 5 child nodes, then I will perform the in-order operation on the node 5 times, once after visiting each child node. This does not make sense to me. Isn't a tree traversal supposed to go through each node once?

Actually, does an in-order traversal even make sense for generic trees? Doesn't it only apply to binary trees, or trees where the "order" is not ambiguous?

  • Why would a binary node be any more likely to have a well-defined order between its children? Nodes of any arity can have either ordered lists or simple sets of children. – Kilian Foth Mar 19 '15 at 7:47
  • You're right. I only considered trees that are ordered because they have a fixed number of children, and hadn't considered other ways of ordering children, like alphabetical for example. So an in-order traversal makes sense now. However, performing an operation on the same node several times still doesn't. – 9a3eedi Mar 19 '15 at 8:13
1

In the algorithm you provided, although it is true that the same in-order operation is performed in the same node multiple times, it is still ran once for each node and each node is visited only once.

Note that this isn't a "in-order" tree traversal, you can't make such a traversal on a ntree, it just doesn't make sense. This is simply a deep-first traversal and the in-order operation is something that is ran after the node has been visited. It has nothing to do with the "in-order functions" that are mentioned elsewhere in on the page.

Maybe I should add, visit is the recursive call in this case, not the in-order operation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.