Progfun: Union two Binary Trees (week 03)

In Progfun assignment of week3 named "objsets", it is required to write some fast-engouh implementation for the union method.

Note, I am here will not show the solution for this question, I'll just give you the key to find the solution yourself.

Here's the Tree objects:

abstract class TweetSet {

    def union(that: TweetSet): TweetSet

    // other methods here..

}

class Empty extends TweetSet {

    def union(that: TweetSet): TweetSet = that

}

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

    // The is the Not-so-fast implementation from the lectures

    def union(that: TweetSet) = ((left union right) union that) incl elem

}

The question again is to find a better solution for the union method (better in terms of performance as the app with such implementation will took too much time to execute)

Well, since I am not so much good in finding a solution in one shot, I go through more than a step..

First I thought in instead of making the `this` tree to include the `that` tree's nodes, I think of the opposite, which is the `that` tree to include the `this` nodes.

I wrote this -not so good -implementation that is coming from (and based on) the foreach implementation; the foreach implementation is:

def foreach(f: Tweet => Unit): Unit = {

    f(elem)

    left.foreach(f)

    right.foreach(f)

}

So, I thought of an implementation like this, but instead of applying some function to each node, no just add each node to `that` tree, So I wrote this initial implementation:

def union(that: TweetSet): TweetSet = {

    var thatVar = that

    this.foreach { x => thatVar = thatVar.incl(x) }

    thatVar

}

WOW, it worked!, So let's enhance it to comply to the courses rules, which among them is don't use vars and use recursion when possible.

The idea above is for each node in the `this` tree, include it to the `that` tree... pretty simple..

To accomplish this by recursion, we need to do the following:

1. `that` should include the element
2. the result of step #1 should be passed again to the recursion method as `that` and ask `left` start the union process over, then ask `right` to start it over again..

def union(that: TweetSet): TweetSet = ??.union(??.union(?? incl elem))

3. replace the ?? above based on your understanding and you will got the solution.