0

How would I write the following Java code in Scala? The intention is to traverse a tree structure and return the first element that matches a predicate.

public class MyObject {

    private String id;
    private List<MyObject> children;

    public MyObject findById(String otherId) {

        if (this.id.equals(otherId)) {
            return this;
        } else {
            for (MyObject child : children) {
                MyObject found = child.findById(otherId);
                if (found != null) {
                    return found;
                }
            }
            return null;
        }
    }

}

The scala would look something like this but I don't know what to put in the else clause.

class MyObject(id: String, children: List[MyObject]) {

    def findById(otherId: String): Option[MyObject] = {
        if (this.id == otherId) {
            Some(this)        
        } else {
            //What goes here?
        }
    }

}
KevinS
  • 7,715
  • 4
  • 38
  • 56

1 Answers1

4

You should implement a tail recursive search, so you won't get a stack overflow:

class MyObject(val id: String, val children: List[MyObject]) {
  def findById(otherId: String): Option[MyObject] = {
    @tailrec
    def recurseOverChildren(list: List[MyObject]): Option[MyObject] = {
      list match {
        case Nil => None
        case head :: tail =>
          if(head.id == otherId) Some(head)
          else recurseOverChildren(tail ++ head.children)
      }
    }
    recurseOverChildren(List(this))
  }
}

The recursion is simple, we just check if the head of the list is the item we're searching for. If not we add it's children to the end of the list. If the list is empty the item is not in the tree. We initialize the search with a list containing one element: the element the function was invoked upon.

This will be a breadth first search, if you would like a depth first search then append the children in front of the list, not at the end.

Community
  • 1
  • 1
Akos Krivachy
  • 4,915
  • 21
  • 28
  • @KevinStembridge No problem. Did you also understand what the code does? I can update my answer with line-by-line details, but didn't know your level of understanding of Scala and recursions in general. – Akos Krivachy Nov 17 '13 at 22:57
  • Thanks for the offer but your answer does a good job of explaining it. Very good answer. – KevinS Nov 17 '13 at 23:03