How to find an element in a tree using scala

Question

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?
        }
    }

}

Answer 1

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.