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?)
Best Answer
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 :
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.
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