10
$\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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\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.

Improve this answer
$\endgroup$
7
  • 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, 2015 at 4:46
  • $\begingroup$ @D.W. What about in-oder? Could you please include that in your answer too? $\endgroup$
    – Renae Lider
    Jul 29, 2015 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, 2015 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, 2015 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, 2015 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

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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