0

I have the following object structure:

case class Node(id:Int,children:List[Node])

Example:

NodeA
    id: 1
    children:[
        NodeA1:
            id: 2
            children:
                NodeA11
                ...
        ]       
        NodeB1:
            id: 3
            children:[]
        NodeC1:
            id: 17
            children: [
                NodeC11:
                    id:11
                    children:[
                        NodeC111:
                            id: 19
                            children: []
                    ]

            ]
        ...

I would like to create a recursive looping to get the Node that has a specific Id but i'm stuck in how to keep running the fuction if the iD isn't found and the object has any object on children list. My function only works to get the first node (ex.: Id = 1).

Here is what i'm trying to do:

def getNode(id:Int, node:Node) : Node = {
    var result:Node = null
    if(node.id == id){
      return node
    } else if(node.children.size > 0 ){
      for(children <- node.children){
        result = getNode(id, children)
        if(result.id == id){
          return result
        }
      }
    }
    return result
}
Improve this question
2
  • Do you really want to return null when nothing is found? Commented Feb 10, 2015 at 16:53
  • it could be null, none or an exception Commented Feb 10, 2015 at 16:55

1 Answer 1

Reset to default
6

Function getNode really should return Option[Node] to account for searches for an id missing in the Node tree.

And in that case you can compose Options of recursive calls:

def getNode(id:Int, node:Node): Option[Node] = 
  if (node.id == id) Some(node)
  else node.children.collectFirst(Function.unlift(getNode(id, _)))

In imperative case you don't need the check for list length: just return None/null after the loop where you check every child (or don't check if there aren't any children).

def getNode(id:Int, node:Node) : Option[Node] = {
  if (node.id == id) Some(node)
  else {
    for (child <- node.children) {
      val result = getNode(id, child)
      // At this point `result` is Some(nodeWeAreLookingFor) 
      // if it is in the subtree of the current `child`
      // or None otherwise
      if (result.isDefined) return result
    }
    None
  }
}

For Java you can of course replace Option with null, but in Scala this idea is naturally modelled by Option

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

So elegant...i was just wondering, how to code the else condition on imperative way? i'm asking because i'm java developer and i would to make a parallel on those languages
@placplacboom I've added a part for the imperative case
inside the for loop, just use return getNode(id, child), no need to verify the Option is define or not.
Just played with Function.unlift, it's awesome!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.