CEng242 Homework 1
Due 1st March 2002

For a given hierarchy represented in a binary tree structure, you are expected to find the list of elements in all of the levels. It is like returning lists of persons in the same level in a company hierarchy. Resulting value will be a list of left to right lists of individuals in the same level of the tree. 

           1                        [ [1] ,
         /   \                        
        /     \
       2       5                      [2,5] ,
      / \     / \
     3   4   2   6                    [3,4,2,6] ,
                / 
               7                      [7] ]

So the function that you will implement will return [[1],[2,5],[3,4,2,6],[7]] for the tree in the example.

You are given the following datatype definition:
datatype 'a Tree = Empty | Node of ('a * 'a Tree * 'a Tree);

You are expected to implement the function getLevels:'a Tree -> 'a list 'a list which get a 'a Tree type value and return a list of level lists as described above.

Sample run:

val tree1=(Node("a",Node("b",Node("c",Empty,Empty),
                             Node("d",Empty,Empty)),
                    Node("e",Empty,Empty)));

getLevels tree1;
val it = [["a"],["b","e"],["c","d"]] : string list list

val tree2=(Node(1,Node(2,Node(3,Empty,Empty),
                         Node(4,Empty,Empty)),
                  Node(5,Node(2,Empty,Empty),
                         Node(6,Node(7,Empty,Empty),Empty))));
getLevels tree2;
val it = [[1],[2,5],[3,4,2,6],[7]] : int list list

You can assume that the tree given to getLevels is non-empty at the top level. You will submit your homework by executing submit242 filename command in Sun WS. domain after we announce that the submission directory is ready. No need to mention, cheating or cooperation in any level is strictly forbidden. Cheaters will be reported to the department management.

1