# Developers Planet

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;
``````

### Answers

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

1. Besides `val rec`, you can also write `fun` and specify the arguments on the left-hand side of the `=`.
2. 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
``````
3. 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)
``````
4. 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.

#### Post Status

Asked in February 2016
Viewed 3,762 times
Voted 10
Answered 2 times