I need to write a recursive program for filter on a set where set is implemented as binary search tree data structure. While trying to design the solution it seems easy for the base case as filter on the empty set should be the empty set but while thinking about the general case I am getting confused and not able to think due to the recursive structure of the data.

Although its told to not to think how recursion works just think about the base case and reduce the larger instance to the base case but I am kind of stuck here. Is there is some mathematical recursive definition of the filter procedure which I can then convert to the corresponding programming structure or how to proceed in these kind of scenarios?

To prove that I gave some thought over it below are the two scenarios which I could think in general:

  1. While writing this a thought to came to my mind to filter the left subset, filter the right subset and the finally the root element and do union of all the three, is this right?
  2. Second option could be like either the filtered set would contain the first element of the set or not, if yes the add the first element to the result and recourse on the remaining set.


From the source:

/** This method takes a predicate and returns a subset of all the elements
 *  in the original set for which the predicate is true.
def filter(p: Tweet => Boolean): TweetSet
def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet
  • $\begingroup$ I take your filter is just $\{x\in S: property(x)\}$, not something like this, right? $\endgroup$ – celtschk Aug 21 '16 at 5:51
  • $\begingroup$ @celtschk yes, also I have updated the question. $\endgroup$ – CodeYogi Aug 21 '16 at 6:04
  • $\begingroup$ Both methods should give equivalent results (whether they give the same result depends on your tree implementation, for example if you rebalance your trees). I'd expect the first algorithm to be faster, but that should depend on the exact implementation of the tree, especially the amount of work you have to do on the merging. $\endgroup$ – celtschk Aug 21 '16 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.