CODEWITHSUNDEEP
validationtypestreesml
easymode
easymode

Reputation: 1

SML - function that checks if a tree datatype is valid or not

datatype tree = br of tree*int*tree | lf

The tree is valid if the values of branches on the left are always lower than the root and branches on the right are always higher. For instance:

valid(br(br(lf,2,lf),1,lf)) = false;
valid(br (br (lf, 2, br (lf, 7, lf)), 8, lf)) = true;

I'm looking for somethine like this, except i have no idea how to compare the integer of inner branches to the integer of roots.

fun valid(lf)=true 
  | valid(br(left,x,right)) = valid(left) andalso valid(right);

EDIT: So far i've come up with this (but it still doesn't check all the integers against all the upper nodes, just 1 node above.. it's close but no cigar)

fun valid(lf)=true 
| valid(br(lf,x,lf)) = true
| valid(br(lf,x,br(left2,z,right2))) = if x<z then valid(br(left2,z,right2)) else false
| valid(br(br(left,y,right),x,lf)) = if y<x then valid(br(left,y,right)) else false
| valid(br(br(left,y,right),x,br(left2,z,right2))) = if y<x andalso x<z then valid(br(left,y,right)) andalso valid(br(left2,z,right2)) else false;

Upvotes: 0

Views: 185

Answers (1)

John Coleman
John Coleman

Reputation: 51998

Assuming that this is homework, I'll give you a hint rather than a complete answer. It would help to first define a function, maybe call it all_nodes which has type

tree * (int -> bool) -> bool

this should be a function which, when passed a tree and a Boolean function on integers returns true if all integers in the tree satisfy the predicate.

Then your function valid should have 4 (rather than 2) clauses. For br(left,x,right) to be valid:

1) left must be valid

2) all integer nodes in left must satisfy that they are < x . This can be checked using all_nodes and an appropriate anonymous function

3) right must be valid

4) all integer nodes in right must be > x, which again can be checked by passing an appropriate anonymous function to all_nodes

On Edit: the above will work but entails a certain amount of inefficiency due to applying two rather than one recursive function to each subtree. An alternative approach would be to define a helper function which only applies to trees of the form br(left,x,right). This helper function could return a tuple of type bool*int*int which tells you whether or not the tree is valid, together with the minimum and the maximum int in the tree. The main function would simply take care of the lf pattern and invoke and interpret the helper function. The crucial point is that at the key recursive step, it is enough to check the max of the left and the min of the right against the int at the node. Some care needs to be taken in how the recursive step is formulated so that you don't call the helper on lf, but it is certainly doable.

Upvotes: 1

Related Questions