Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?)

screenshot

share|improve this question
    
Why do you think it'll be other than Sorted? –  PhD Mar 8 '12 at 8:16
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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