import Tree.*;

class Tree<A> {
    case Empty;
    case Branch(A elem, Tree<A> left, Tree<A> right);

    public boolean contains((A, A) -> boolean less, A x) {
        switch (this) {
        case Empty:
            return false;
        case Branch(A elem, Tree<A> l, Tree<A> r):
            if (less(x, elem)) 
                return l.contains(less, x);
            else if (less(elem, x))
                return r.contains(less, x);
            else 
                return true;
        }
    }

    public Tree<A> insert((A, A) -> boolean less, A x) {
        switch (this) {
        case Empty:
            return Branch(x, Empty, Empty);
        case Branch(A elem, Tree<A> l, Tree<A> r):
            if (less(x, elem)) 
                return Branch(elem, l.insert(less, x), r);
            else if (less(elem, x))
                return Branch(elem, l, r.insert(less, x));
            else 
                return this;
        }
    }

    Tree<A> goRight() {
        switch (this) {
        case Empty:
	    return this;
	case Branch(_, _, Tree<A> r):
	    return r.goRight();
	}
    }
}

public class Test {
  public static void main(String[] args) {
    Tree<int> t = Branch(2,
			 Branch(1, Empty, Empty),
			 Branch(3, Empty, Empty));
    t.insert(fun(int a, int b) -> boolean { return a < b; }, 4);
  }
}