generate a tree in scala

data-structures, scala, tree

Solution

Just something like

val tree = Branch(
             Branch(
               Leaf(12),
               Branch(
                 Leaf(3),
                 Leaf(4))),
             Leaf(8))

That should be the tree

      *
    /   \
   *     8
  /  \
 12   *
     /  \
     3   4

You can reuse that in a bigger tree. The point is that you build bottom up, you cannot at something at the bottom, that requires creating a new tree from scratch

val biggerTree = Branch(Branch(something, tree), stillSomethingElse)

In complement of @dhg's answer, a variant which generates a tree with a given number of branches (note: there are always one more leaves than there are branches, so the total number branches + leaves is always odd). That should make testing straightforward

def randomTree(branchCount: Int): Tree[Int] =
  if(branchCount == 0) Leaf(0) // whatever, you can put a random here
  else {
     val branchCountAtLeft = util.Random.nextInt(branchCount) 
          // between 0 and branchCount - 1
     val branchCountAtRight = branchCount - 1 - branchCountAtLeft
     Branch(randomTree(branchCountAtLeft), randomTree(branchCountAtRight))
  }

Problem

I am learning Scala and the book that I am using provides an exercise that asks me to define some functions on a tree structure. The tree is defined as: ``` sealed trait Tree[+A] case class Leaf[A](value: A) extends Tree[A] case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A] ``` One of the exercise is to count the number of nodes in the tree. I wrote the function but I can not check if it is working because I do not have any example of tree. How can I generate a small tree that I can use to test my code? It is probably possible to add one element at the time to the tree but it seems like a lot of work.

Original source