find is a function that operates on a tree and returns an option (None or SOME(X)).. A tree = EMPTY | Node(L,X,R) where L,R are trees, X is an integer. L is the left subtree, R is the right subtree.

The above function finds the ith element of an in-order traversal of tree T, using a helper
function size, which finds the size of any given tree. Assume size(T) has O(n) work where
n is the number of nodes in T\


type of find : int*tree -> Option(int)

(*operating on a case of an empty tree*)
fun find(i, Empty) = NONE


(*operating on a full tree*)
fun find(i, Node(l, x, r)) =
    case find(i, l) of (recursive call to find (i,L) where
    SOME(y) => SOME(y)
    | NONE => if i = (size l) + 1 then SOME(x)
              else find(i - (size l) - 1, r)

in java it's

#find value at index i  in the inorder rep of
int find_at_i(int i, Tree t) {
    int j =  find_at_i(t.left_tree)
    switch(j)
	{
      case -1 => if(i = t.left_tree.size() + 1)
                 then return t.val
                 else return find_at_i(i - t.left_tree.size() - 1, t.right_tree)
	  default => return j;
    }
}