The following Scala code is provided:
/**
* A class to represent tweets.
*/
class Tweet(val user: String, val text: String, val retweets: Int):
override def toString: String =
"User: " + user + "\n" +
"Text: " + text + " [" + retweets + "]"
/** This represents a set of objects of type `Tweet` in the form of a binary search
* tree. Every branch in the tree has two children (two `TweetSet`s). There is an
* invariant which always holds: for every branch `b`, all elements in the left
* subtree are smaller than the tweet at `b`. The elements in the right subtree are
* larger.
*/
abstract class TweetSet extends TweetSetInterface:
/**
* Tests if `tweet` exists in this `TweetSet`.
*/
def contains(tweet: Tweet): Boolean
class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet:
def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = ???
/**
* The following methods are already implemented
*/
def contains(x: Tweet): Boolean =
if x.text < elem.text then
left.contains(x)
else if elem.text < x.text then
right.contains(x)
else true
My question is for the contains method, when/why can it return a false when it reaches to the null(empty leaf node)?
when/why can it return a false when it reaches to the null(empty leaf node)?
It can't. If it ever reached null, this implementation would throw an exception. Instead, given the name, it's likely there is also a
class Empty extends TweetSet which defines the same method as def contains(tweet: Tweet): Boolean = false.
(Searching for a part of this code confirmed it, but I am not linking the repo I found because it would be a spoiler for you.)