sarthak sarthak - 15 days ago 5
Scala Question

Union of Trees in Scala

I am trying to take union of two trees using the union method. For the purposes of checking the code I added the print statements inside the method. But the print of

acc
shows that it is not changing with the recrsion. I do not understand why is this happening. Can someone please explain.

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

def union(that: TweetSet): TweetSet =
{
def unionRec(set:TweetSet,acc:TweetSet): TweetSet =
{
if (set.isEmpty)
return acc
else
{
acc.foreach(x=> println(x))
println("####################")
set.foreach(x=>println(x))
println("####################")
unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
return acc
}
}
unionRec(this,that)
}

def takeLeft: TweetSet =
{
return left
}

def takeRight: TweetSet =
{
return right
}
def rootTweet: Tweet =
{
return elem
}
def incl(x: Tweet): TweetSet = {
if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
else this
}
def isEmpty: Boolean = false
def foreach(f: Tweet => Unit): Unit = {
f(elem)
left.foreach(f)
right.foreach(f)
}
}
class Empty extends TweetSet {
def isEmpty: Boolean = true
}

Answer

You are doing the exact same mistake as you did in your last question (Adding an element to a tree in scala). You are throwing away the result of your unionRec-call. Remember that TweetSet is immutable, so acc will never change!

These two lines:

unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
return acc

Has to be changed to this:

return unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))