Your answer is one click away!

user1313623 February 2016
### Checking whether a given value exists in a binary tree

I am new to SML. I am trying to check whether a given value exist in the binary tree or not. Below is the snippet of the code. Upon execution it gives

```
Warning : match nonexhaustive (n,Node (t1, j, t2)) => ...
```

I cannot understand why it is showing this way. I guess I have covered all possible case. Can anyone give me hint or link which will be helpful to remove this warning.

```
datatype inttree = Empty | Node of inttree * int * inttree;
(*find(n,K) here n is the key that we have to find in inttree K*)
val rec find = fn(n, Node(t1,j,t2)) =>
let
val t = Node(t1, j, t2)
val compare = fn(i,j) => i = j
val find' =
fn (n,Empty) => false (* if we have reached the empty node then we are not able to find the key therefore return false *)
| (n,Node(t1,j,t2)) =>
if compare(n,j)
then true (* if value n and j are equal we have found the key n in the tree*)
else find(n,t1) orelse find(n,t2) (* if the value is not equal check in left subtree if found return true else check in the right subtree*)
in
find'(n,t)
end;
```

John Coleman February 2016

Given your datatype declaration, a fairly direct recursive approach is possible. Since this seems to be homework, I don't want to give a complete solution, but here is a function which has a similar flavor:

```
fun allEven Empty = true
| allEven (Node(t1,i,t2)) =
if i mod 2 = 1 then false
else allEven t1 andalso allEven t2;
```

This function returns true or false depending on whether or not all integers in the tree are even. It has a basis case

```
allEven Empty = true
```

(true since there are no odd numbers in an empty tree to serve as counter-examples) and a recursive case

```
allEven (Node(t1,i,t2)) =
if i mod 2 = 1 then false
else allEven t1 andalso allEven t2;
```

If the integer at the node is odd, return false -- otherwise return true if the recursive call to both branches evaluate to true.

Typical runs:

```
- allEven (Node(Node(Empty,3,Empty),5,Node(Node(Empty,6,Empty),7,Empty)));
val it = false : bool
- allEven (Node(Node(Empty,4,Empty),2,Node(Node(Empty,6,Empty),8,Empty)));
val it = true : bool
```

Your function should be about this long and follow the same basic recursive pattern.

Simon Shine February 2016

- Besides
`val rec`

, you can also write`fun`

and specify the arguments on the left-hand side of the`=`

. The helper function

`compare`

is largely redundant. You might as well use`=`

. Also, what one would call a compare function in ML is usually one that returns the type*order*, having the values`LESS`

,`EQUALS`

and`GREATER`

:`- Int.compare (3, 5); > val it = LESS : order`

When writing an

`if ... then true else ...`

or similar statement that returns the type*bool*, you might as well just use the combinators`orelse`

and`andalso`

. For example, you can replace the following:`if compare(n,j) then true else find(n,t1) orelse find(n,t2)`

with:

`n = j orelse find (n, t1) orelse find (n, t2)`

Much like the built-in functions

`List.exists`

and`List.all`

take a function as predicate and scans a list in the attempt to prove either that at least one element exists for which this is true, or that it is true for all elements, you can make functions`treeExists`

and`treeForall`

:`datatype intTree = Empty | Node of inttree * int * inttree; fun treeExists f Empty = false | treeExists f (Node (leftTree, x, rightTree)) = f x orelse treeExists f leftTree orelse treeExists f rightTree fun treeForall f Empty = true | treeForall f (Node (leftTree, x, rightTree)) = f x andalso treeForall f leftTree andalso treeExists f rightTree`

Making functions

`find`

and`allEven`

has now become simpler:`fun find (x, tree) = treeExists (fn y => x = y) tree fun allEven tree = treeForall (fn x => x mod 2 = 0) tree`

since all the recursion has been left to new library functions.

Asked in February 2016

Viewed 3,762 times

Voted 10

Answered 2 times

Viewed 3,762 times

Voted 10

Answered 2 times