Binary Trees - Scala Recursion for the union of trees

Here is the implementation of binary trees that I have seen in Martin Odersky's video lectures on Coursera, week 3:

abstract class IntSet
{
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def union(other: IntSet): IntSet
}

object Empty extends IntSet
{
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
  def union(other: IntSet): IntSet = other

  override def toString = "."
}

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet
{
  def contains(x: Int): Boolean =
    if (x<elem) left contains x
    else if (x > elem) right contains x
    else true

  def incl(x: Int): IntSet =
    if (x<elem) new NonEmpty(elem, left incl x, right)
    else if (x > elem) new NonEmpty(elem, left, right incl x)
    else this

  def union(other: IntSet): IntSet =
    ((left union right) union other) incl elem

  override def toString = "{" + left + elem + right + "}"
}

So Empty and NonEmpty follow the standards outlined by the IntSet. What I am interested in, is the union method in the NonEmpty class. I would like to understand how it works.

I have made a small depiction below to explain my thinking process:

To me it appears as if there is an infinite loop there. But I am more than certain that I have made an evaluation mistake somewhere below:

1. ((L_1 U R_1) U O) incl e1
2. ((L_3 U R_3) U R_1) incl e3
3. (E U R_1) incl e3
4. 2.
5. 3.
6. 2. etc. etc.