7
$\begingroup$

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.

enter image description here

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Adam R. Nelson Jul 29 '15 at 4:46
  • $\begingroup$ @D.W. What about in-oder? Could you please include that in your answer too? $\endgroup$ – Renae Lider Jul 29 '15 at 4:46
  • $\begingroup$ @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. $\endgroup$ – Renae Lider Jul 29 '15 at 4:50
  • $\begingroup$ @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. $\endgroup$ – Adam R. Nelson Jul 29 '15 at 4:56
  • 2
    $\begingroup$ @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. $\endgroup$ – Raphael Jul 29 '15 at 9:31
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Dec 25 '16 at 20:40
  • $\begingroup$ Am not clear about insert / update procedure of ordered n- ary tree. Can u share the code? $\endgroup$ – overexchange Dec 25 '16 at 21:45

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.