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
    Commented Mar 8, 2012 at 8:16

2 Answers 2


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]].

Your Answer

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

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