scala - Recursive set union: how does it work really?

Question

I am currently taking the Scala course on Coursera on my free time after work, in an attempt to finally give a try to functional programming. I am currently working on an assignment where we are supposed to "calculate" the union of two sets that contain some object. I am intentionally omitting details as it's not really important to what I am trying to ask here. What is relevant, however, is that the sets are defined as binary trees, with each node containing an element, and two subtrees.

That being the case; the example union in the lecture is as follows:

def union(other:BTSet) :BTSet = ((left union right) union other) incl element

Question1: Quite frankly, even after having read the relevant FAQ and other forum threads, I still don't understand how and why this function works. There is absolutely no "action" done here in union implementation besides adding (the incl call) the element at the head node, it simply calls itself over and over again. I would be very appreciative of some explanation...

Question2: The course forum contains many posts stating that this solution is not efficient at all, and that it is not good enough. Seeing as I don't understand how it works to begin with I don't really understand why it's not good enough.

PLEASE NOTE that I do not, in any way, ask for a spoiler for the assignment solution. I am more than willing to "do the work for the grade" but I simply don't understand what I am supposed to do here. I don't believe the instructions and guidance provided in the course are adequate to wrap your head around the quirks of functional programming, thus I welcome any comments/answers that address how to think right rather than how to code right.

Answer 1

  A
 /   union  D
B   C

((B union C) union D) incl A
  ^^^^^^^^^......................................assume it works

(  B             )
(       union D ) incl A
(     C          )

(((0 union C) union D) incl B) incl A
   ^^^^^^^^^.....................................just C

(((C union D) incl B) incl A
   ^^^^^^^^^.....................................expand

((((0 union 0) union D) incl C) incl B) incl A
    ^^^^^^^^^....................................just 0

(((0 union D) incl C) incl B) incl A
   ^^^^^^^^^.....................................just D

((D incl C) incl B) incl A
^^^^^^^^^^^^^^^^^^^^^^^^^^.......................all incl now

Just write it out step-by step. Now you see that union reduces to a bunch of incl statements applied to the right-hand argument.