Implementing a generic and covariant Set in Scala

I'm struggling with manually implementing a simple purely functional Set that's also generic and covariant on its type parameter:

• Set must be a trait, allowing for multiple implementations.
• it must be covariant on the type of the element it contains.
• an implementation's type must not be lost when calling methods that return a new Set.

The first two points are fairly trivial and simply mean that the trait should look something like:

trait Set[+A] {
  def isEmpty: Boolean
  def insert[B >: A](b: B)(implicit order: Ordering[B]): Set[B]
  def contains[B >: A](b: B)(implicit order: Ordering[B]): Boolean
}

The problem with this implementation is that insert, for example, will always return an instance of Set. If I were to write a specialised implementation of Set with useful helper methods, its type would be lost as soon as an element was inserted in it.

This is what I've come up with, which seems to work but I still find confusing and can't help but feel is over-complicated (recursive higher kinded types!):

trait Set[+A, Repr[+X] <: Set[X, Repr]] {
  this: Repr[A] =>

  def isEmpty: Boolean
  def insert[B >: A](b: B)(implicit order: Ordering[B]): Repr[B]
  def contains[B >: A](b: B)(implicit order: Ordering[B]): Boolean
}

Here's a sample implementation using a simple binary tree:

sealed trait CustomSet[+A] extends Set[A, CustomSet]

case class Node[A](value: A, left: CustomSet[A], right: CustomSet[A]) extends CustomSet[A] {
  override def isEmpty = false

  override def insert[B >: A](b: B)(implicit order: Ordering[B]) =
    if(order.lt(b, value))      Node(value, left.insert(b), right)
    else if(order.gt(b, value)) Node(value, left, right.insert(b))
    else                        this

  override def contains[B >: A](b: B)(implicit order: Ordering[B]) =
    if(order.lt(b, value))      left.contains(b)
    else if(order.gt(b, value)) right.contains(b)
    else                        true
}

case object Leaf extends CustomSet[Nothing] {
  override def isEmpty                                        = true
  override def insert[B](b: B)(implicit order: Ordering[B])   = Node(b, Leaf, Leaf)
  override def contains[B](b: B)(implicit order: Ordering[B]) = false
}

The questions that I have are:

• I don't believe the self-type is strictly necessary here. Are there good reasons to leave it? to remove it?
• is this the correct / best / simplest way to implement what I'm trying to write? Are there any alternatives?