# In order traversal of M way Trees

If we have a 4 way tree such as the one shown below, and we do an in order traversal, what would the output of the in-order traversal be for an M-way tree?

In which order would the nodes be visited? When would the value in the node be processed (upon first visit or upon second visit)?

(As a concrete example, what would the step by step procedure for the in order traversal be for the example tree shown below?) • Why do you think it'll be other than Sorted? – PhD Mar 8 '12 at 8:16

I believe the in order traversal of m-way trees can be generalized. Lets take the example of the tree you have provided. Following are the steps for that :

1. Go to the left most node first and print its first element. Then check if there is any subtree between this element and the next element in that node. If it exists then apply the same approach on that sub-tree, else print element. Similarly move through all the elements in that node. Since in your tree there is no sub-tree in your left most node so print all the elements. Thus the output of first step will be : 2, 5, 6.

2. Then apply same algo in the parent node and move up towards your root node recursively.

Thus the output of the in-order traversal of your tree should be :

2,5,6, 7, 9,12,17, 20, 26,31,39, 45, 46,53,71

You can refer to this ppt for more info : In order Traversal of M-Way Trees

There is no obvious in-order traversal for rose trees (m-way trees), unlike for pre- or post-order traversals, because while you clearly need to process the leftmost subtree first and the rightmost subtree last, it's not clear when you should process the current node.

I ended up saying "process the leftmost subtree, then the current node, then the remaining subtrees in order". When the rose tree's nodes all have two or less subtrees, that ends up with the same traversal as a binary tree's in-order traversal.

Assuming that each node in your diagram has an array value (I don't find your diagram very clear), the traversal I describe would yield `[[2,5,6],[7,20,45],[9,12,17],[26,31,39],[46,53,71]]`.