generate a tree in scala

Question

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.

Answer 1

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))
  }

Answer 2

@Didier's answer is good for making your own trees by hand, but if you want to automatically generate trees, you can do so with a little recursive generator:

def generate(p: Double): Tree[Int] = {
  if (util.Random.nextDouble < p)
    Branch(generate(p), generate(p))
  else
    Leaf(0)
}

Then you just do:

val t = generate(0.5)
println(t)

and you'll get a random tree. Lowering p will make the trees tend smaller; raising it will make them tend bigger.

Clearly this will make trees with all leafs the same value. If you want random leaf values, try:

 Leaf(util.Random.nextInt(100))