Scala: How to compute the sum of all elements in the leaves of a Binary Tree?

Question

I'm learning Scala by working the exercises from the book "Scala for the Impatient". Given the following way to model binary trees with case classes, one question asks to compute the sum of all elements in the leaves.

sealed abstract class BinaryTree
case class Leaf(value: Int) extends BinaryTree
case class Node(left: BinaryTree, right: BinaryTree) extends BinaryTree

My solution is as follows and works as expected. However, I'm using a MutableList and because Scala favors immutability, I am wondering if there's a way to solve the problem using List?

def leafSum(tree: BinaryTree): Int = {
  collectLeaves(tree) { MutableList[Int]() }.sum
}

private def collectLeaves(tree: BinaryTree)(leaves: MutableList[Int]): MutableList[Int] = tree match {
  case Node(left, right) =>
      collectLeaves(left)(leaves); collectLeaves(right)(leaves)
  case Leaf(value) => leaves += value
}

Answer 1

Using a List is not a good idea for the reason that when you concatenate two lists, you will have to copy their content so an O(n) complexity operation each time you encounter a Node.

If you really want to do it with Lists, you could do it like this:

def leafSum(tree: BinaryTree): Int = {
  collectLeaves(tree).sum
}

private def collectLeaves(tree: BinaryTree): List[Int] = tree match {
  case Node(left, right) => collectLeaves(left) ::: collectLeaves(right)
  case Leaf(value) => List(value)
}

although in my opinion it's better to compute directly the sum as you don't need to store the values in the leaves:

def sum(tree: BinaryTree): Int = tree match {
  case Node(left, right) => sum(left) + sum(right)
  case Leaf(value) => value
}

Answer 2

Here's a recursive approach that doesn't use a helper method that I think is fairly elegant. Note it's not tail recursive and will run out of memory for large inputs.

def leafSum(tree: BinaryTree): Int = tree match{
  case leaf:Leaf => leaf.value
  case node:Node => leafSum(node.left) + leafSum(node.right)
}