new NodeBase := class {
  new height := -1; # height of an empty tree is defined as -1
  # placeholders for abstract methods
  new insert := -1;
  new contains := -1;
  new traverse := -1;
};

new Empty := class NodeBase {
  insert := lambda k {
    ret := make_leaf@k;
  };

  contains := lambda k {
    ret := false;
  };

  traverse := class { };
};

new max := lambda a { ret := lambda b {
  ifelse a >= b { ret := a; } { ret := b; }
}; };

new make_internal := lambda key { ret := lambda left { ret := lambda right {
  ret := class NodeBase {
    height := max@(left!height)@(right!height) + 1;

    insert := lambda newkey {
      ifelse newkey < key {
        ret := make_internal @ key @ (left!insert @ newkey) @ right;
      } {
        ret := make_internal @ key @ left @ (right!insert @ newkey);
      }
      height := max@(left!height)@(right!height) + 1;
    };

    contains := lambda searchkey {
      ifelse searchkey = key { ret := true; }
      {
        ifelse searchkey < key
          { ret := left!contains @ searchkey; }
          { ret := right!contains @ searchkey; }
      }
    };

    traverse := class {
      left!traverse!;
      write key;
      right!traverse!;
    };
  }!;
};};};

new make_leaf := lambda key {
  ret := make_internal @ key @ Empty! @ Empty!;
};

new BST := class {
  new root := Empty!;
  new size := 0;
  new height := -1;

  new insert := lambda k {
    if not root!contains @ k {
      root := root!insert @ k;
      size := size + 1;
      height := root!height;
    }
  };

  new contains := lambda k {
    ret := root!contains@k;
  };

  new print := class {
    "begin in-order tree traversal"
    (root!traverse)!;
    "end in-order tree traversal"
  };
};

# create tree with 10 items and test
new t1 := BST!;
t1!insert@30;
t1!insert@80;
t1!insert@90;
t1!insert@20;
t1!insert@40;
t1!insert@70;
t1!insert@10;
t1!insert@100;
t1!insert@90;
t1!insert@60;
t1!insert@50;
t1!print!;
write t1!size;
write t1!contains@10;
write t1!contains@15;

# create tree with 1000 random items and check height and size
new i := 0;
new t2 := BST!;
while i < 1000 {
  t2!insert@(rand@1000);
  i := i + 1;
}
"size should be around 600"
write t2!size;
"height should be around 18, depending on size"
write t2!height;