algorithm - Traverse tree in a functional way -

i've implemented basic mutable tree in scala , want traverse in functional way in order search element, don't know how implement it. want algorithm tail recursive if possible.

the tree structure value , list of leafs trees.

any appreciated.

this code have (focus on getopt method):

package main  import scala.collection.mutable.listbuffer  sealed trait tree[node] {    val node: node    val parent: option[tree[node]]    val children: listbuffer[tree[node]]    def add(n: node): tree[node]    def size: int    def getopt(p: (node) => boolean): option[tree[node]]    override def tostring = {     s"""[$node${if (children.isempty) "" else s", children: $children"}]"""   } }  case class concretetree(override val node: int) extends tree[int] {    override val children = listbuffer[tree[int]]()    override val parent: option[tree[int]] = none    override def add(n: int): concretetree = {     val newnode = new concretetree(n) {override val parent: option[tree[int]] = some(this)}     children += newnode     newnode   }    override def size: int = {     def _size(t: tree[int]): int = {       1 + t.children.foldleft(0)((sum, tree) => sum + _size(tree))     }     _size(this)   }    // method not correct   override def getopt(p: (int) => boolean): option[tree[int]] = {     def _getopt(tree: tree[int], p: (int) => boolean): option[tree[int]] = {       tree.children.map {         t =>           if(p(t.node)) some(t) else t.children.map(_getopt(_, p))       }     }   } }  object main {    def main(args: array[string]) {     val tree1 = concretetree(1)     val tree2 = tree1.add(2)     val tree3 = tree1.add(3)      println(tree1.getopt(_ == 2))   } } 

@doertsch answer best approach have @ moment.

i go more flexible , implement generic function produce lazy stream of flattened tree, lot of later work become easier. this:

def traverse[node](tree: tree[node]): stream[tree[node]] =    tree #:: (tree.children map traverse).fold(stream.empty)(_ ++ _) 

then getopt reduces this:

override def getopt(p: (int) => boolean): option[tree[int]] =   traverse(tree) find {x => p(x.node)} 

simplifying further, if you're interested in data without tree structure, can stream of nodes, giving you:

def nodes[node](tree: tree[node]): stream[node] = traverse(tree) map (_.node)  def getnode(p: (int) => boolean): option[int] = nodes(tree) find p 

this opens other possibilities concise , readable code nodes(tree) filter (_ > 3), nodes(tree).sum, nodes(tree) contains 12, , similar expressions.