CODEWITHSUNDEEP
algorithmscaladata-structures
Pbk243
Pbk243

Reputation: 51

How to return a list all paths(Branches) of nodes that are in a binary tree using Scala?

I have a trait tree defined as follow:

sealed trait Tree[+T] extends Product with Serializable
final case object Leaf extends Tree[Nothing]
final case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

I am new to FP and scala, I would like to know what is the best and optimal way to retrieve all possible paths starting from the root for a given tree. for example for the tree:

val x = Node(1,Node(2, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))
val paths  = findPaths(x)
paths will have the list of lists = List((1, 2), List(1, 3, 4))

of course, the tree will be much larger.

Upvotes: 0

Views: 401

Answers (1)

jwvh
jwvh

Reputation: 51271

Five different possible branches.

def allPaths[A](tree:Tree[A]):List[List[A]] = tree match {
  case Leaf => Nil
  case Node(v,Leaf,Leaf) => List(v::Nil)
  case Node(v,Leaf,rgt)  => allPaths(rgt).map(v::_)
  case Node(v,lft, Leaf) => allPaths(lft).map(v::_)
  case Node(v,lft, rgt)  => (allPaths(lft) ++ allPaths(rgt)).map(v::_)
}

testing:

val x = Node(1,Node(2, Leaf, Leaf), Node(3, Leaf, Node(4, Leaf, Leaf)))
allPaths(x)
//res0: List[List[Int]] = List(List(1, 2), List(1, 3, 4))

Upvotes: 1

Related Questions