# What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and right child. If it can be used for n-ary trees, how?

An n-ary tree has 1 parent and n children at any given node. Where n can be any whole number for each node.

Please use the figure below to explain this, if you need one.

No, it's not limited to binary trees. Yes, pre-order and post-order can be used for $n$-ary trees. You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function". We assume that the for-loop will iterate through the children in the order they are found in the data-structure: typically, in left-to-right order, for a diagram such as you have shown.

In fact, this is already described in the Wikipedia article on tree traversals: see https://en.wikipedia.org/wiki/Tree_traversal#Generic_tree, which describes exactly how to generalize this to $n$-ary trees. Pre-order traversal is one where the pre-order operation is "Display the current node" and the post-order operation is "Do nothing". Post-order traversal is one where the pre-order operation is "Do nothing" and the post-order operation is "Display the current node".

In-order traversal is a special case. It probably only makes sense for binary trees. While there are several different possible ways that one could define in-order traversal for $n$-ary trees, each of those feels a bit odd and unnatural and probably not terribly useful in practice. So, it's probably best to think of in-order traversal as being specific to binary trees; if you want to do something akin in-order traversal for a $n$-ary tree, you'll need to decide exactly what you mean by that, as there's no standard meaning for that.

• Also worth noting that the one kind of traversal that doesn't work for $n$-ary trees is inorder; there is no meaningful equivalent of inorder traversal for a node with an odd number of children. – Adam R. Nelson Jul 29 '15 at 4:46
• @D.W. What about in-oder? Could you please include that in your answer too? – Renae Lider Jul 29 '15 at 4:46
• @AdamR.Nelson How does it work for an even number other than two? For binary it is Left-Root-Right. I don't know how it will work for, say, a quadtree. – Renae Lider Jul 29 '15 at 4:50
• @RenaeLider Given children named A, B, C, and D (from left to right), you could do something resembling inorder traversal of a quadtree by traversing A-B-Root-C-D. But I don't think there is any useful application of this. – Adam R. Nelson Jul 29 '15 at 4:56
• @AdamR.Nelson You can define in-order for the general case by saying that you visit the parent after the first child, then the other children. Maybe not very meaningful, but possible. – Raphael Jul 29 '15 at 9:31

There are many exotic data structures used all over CS with many variants. There was some similar recent question (now deleted) about traversing n-ary trees in an ordered way by overexchange. It appears that most or many n-ary trees in the literature studied tend not to be ordered. However, as an alternative pov / exceptional / "edge" case on the other detailed answer, there are cases of ordered n-ary trees that are not "odd and unnatural and probably not terribly useful in practice". Here is one ref; there are likely many other cases, although it's possible they are not in widespread use.

[1] n-ary ordered trees / P Mateti 7140 course notes

• ps another way to think of ordered n-ary trees is simply that edges are labelled and have orderings accessable to the algorithm on traversal. – vzn Dec 25 '16 at 20:40
• Am not clear about insert / update procedure of ordered n- ary tree. Can u share the code? – overexchange Dec 25 '16 at 21:45