rc dfs

dfsRecursive.scala

import scala.annotation.tailrec

trait Tree[+T] {val value: T}
case class Node[+T](value: T, children:List[Tree[T]]) extends Tree[T]
case class Leaf[+T](value: T) extends Tree[T]

// returns Some(Node) or Some(Leaf) if targetValue is found, else None
// usage: use 'map' or 'foreach' to get the node from the result eg.
// getNodeInTree('g',tree).foreach{ node => println(s"Found a node: $node") }
def getNodeWhereTarget[T](target: T, tree:Tree[T]):Option[Tree[T]] = {
  @tailrec
  def dfsUntilFound(target: T, stack: List[Tree[T]], setAncestors:Set[T]): Option[Tree[T]] = { stack match {
    case Nil => None
    case Leaf(value)::t => {
      println(value)
      if(value==target) Some(Leaf(value)) else dfsUntilFound(target, t, setAncestors)
    }
    case Node(value, children)::t => {
      println(value)
      if(setAncestors.contains(value)) return None
      val ancestors:Set[T] = setAncestors + value
      if(value==target) Some(Node(value,children)) else dfsUntilFound(target, children++t,ancestors)
    }
    case _ => throw new Error("bad stack passed to dfsUntilFound")
    }
  }
  dfsUntilFound(target, List(tree), Set.empty)
}
//
val d = new Node('d', Nil)
var e = new Node('e', Nil)  // the non-cyclic version of node
val f = new Node('f', Nil)
val h = new Node('h', Nil)
val g = new Node('g', List(h))
val c = new Node('c', List(g))
val b = new Node('b', List(d,e,f))
val a = new Node('a', List(b,c))
e = new Node('e', List(a)) // introduces cycle
//val a = new Node('a', List(Node('b',List(Node('d', Nil), Node('e', Nil), Node('f', Nil))), Node('c', List(Node('g', List(Node('h', Nil))))) ))
// is equivalent to the non-cyclic version


getNodeWhereTarget('g',a)
//getNodeWhereTarget('g',a).foreach {
//  node => {
//    val value = node.value
//    println(s"Found a node called: $value")
//  }
//}