Well, I am asked to do the next thing:

To define a binary tree which can contain 2 different types: ('a,'b) abtree and these are the requirements:

1. Any inner vertex (not a leaf) must be of the type 'a or 'b and the leafs have no value.

2. For every path in the tree all 'a values must appear before the 'b value: examples of paths:

   'a->'a->'a-'b (legal)
   'a->'b->'b (legal)
   'a->'a->'a (legal)
   'b->'b->'b (legal)
   'a->'b->'a (ILLEGAL)
   

and also I need to define another tree which is like the one described above but now I have got also 'c and in the second requirement it says that for every path I 'a values appear before the 'b values and all the 'b values appear before the 'c values.

First, I am not sure how to define binary trees to have more than 1 type in them. I mean the simplest binary tree is:

datatype 'a tree =
          leaf
         | br of 'a * 'a tree * 'a tree;

And also how I can define a tree to have these requirements.

Any help will be appreciated.

Thanks.