# Binary tree implementation in Scala

This is my implementation of a binary tree in Scala. How can this be made better?

abstract class BinaryTreeNode[+A]

case class MyBinaryTreeNode[A](var data: A,var left: BinaryTreeNode[A],var right: BinaryTreeNode[A]) (implicit ordering: Ordering[A]) extends BinaryTreeNode[A] {

override def toString = data + " " + left.toString + " " + right.toString
}

case object MyNilNode extends BinaryTreeNode[Nothing]

def isBST(implicit order: Ordering[A]): Boolean = {
}

def isBSTHelper(node: BinaryTreeNode[A])(implicit order: Ordering[A]): (Boolean, A, A) = {
node match {
case MyNilNode =>
return (true, null.asInstanceOf[A], null.asInstanceOf[A])
case MyBinaryTreeNode(data, lNode, rNode) =>
if(lNode == MyNilNode && rNode == MyNilNode) {
return (true, data, data)
}

val leftResult = this.isBSTHelper(lNode)(order)
val rightResult = this.isBSTHelper(rNode)(order)
return (leftResult._1 && rightResult._1 && data >= leftResult._3 && data <= rightResult._2,
leftResult._2,
rightResult._3)
}
}
}


You haven't actually implemented a binary tree. But I'll make some points about your existing code before explaining what is missing.

## That's not a node, it's a tree

1. Your base class is a node when it should be a tree
2. Wrapping the nodes in a tree class which knows nothing other than it contains nodes is artificial and obstructive

Like many algebraic data types, a binary tree is a recursive type. A node is a tree (one which can hold other trees). Nil/Empty is a tree.

Instead of working with that, you have an inflexible wrapper class Tree and a set of case classes which implements nodes. That incurs many penalties. For a start, you have no representation in your type system of the empty tree. Secondly, you lose the ability to create simple, elegantly recursive methods for your case classes.

Look how much simpler your code can be if you work with that, rather than fight it:

abstract class BinaryTree[+A] {
def isEmpty: Boolean
def isValid: Boolean
}

case object EmptyTree extends BinaryTree[Nothing] {
def isEmpty = true
def isValid = true
}

case class NonEmptyTree[A](
var data: A,
var left: BinaryTree[A],
var right: BinaryTree[A])
(implicit ord: Ordering[A]) extends BinaryTree[A] {
def isEmpty = false
def isValid: Boolean = {
import ord._
def isValidWith(f: A => Boolean, t: BinaryTree[A]): Boolean = t match {
case NonEmptyTree(that, _, _) => f(that) && t.isValid
case EmptyTree => true
}
isValidWith(data < _, left) && isValidWith(data > _, right)
}
}


See how this works with the actual class hierarchy to build comprehensive tree functions simply and recursively? It should be fairly obvious how you could add depth or size methods.

You don't need that wrapper class. What I do recommend is

1. Make the abstract class sealed (improves pattern matching performance and keeps the type sound).
2. Create a BinaryTree companion object containing an apply factory method for creating trees.
3. Make the constructors for BinaryTree and EmptyTree private (if the user can create them directly, they might create invalid trees).
4. Make the class immutable. Turn each var into a val.

You may balk at that last point but modifying the data held at any one node is a dangerous and pointless thing to do. The way binary trees work, it doesn't even make sense. When adding a value, the only places you would want to change left or right is at the node where you insert the value in place of an empty tree (possibly having to move the left branch to the right branch, to preserve ordering). Adding a value to an immutable tree is only marginally more complicated than to a mutable one and much safer. Also, you regain the option of variance (if you want it, although I recommend against).

My final recommendation: throw away that isBST/isValid method. It's pointless...

## That's not an implementation

Nothing in your code actually implements a binary tree. All you've done is provide a shell into which data has to be manually inserted, with a validation method to check whether the manually-constructed tree looks like a binary tree.

But the rules for adding values to an ordered binary tree are simple (OK, more complex if it's a balanced tree). Your type should know how to do that. If you think about it, it shouldn't be hard to create an add method along the same lines as isValid. I'll start it off for you

sealed abstract class BinaryTree[+A] {
def isEmpty: Boolean
def isValid: Boolean
}

case object EmptyTree extends BinaryTree[Nothing] {
def isEmpty = true
def isValid = true
def add[A](a: A): BinaryTree[A] = NonEmptyTree(a, EmptyTree, EmptyTree)
}

case class NonEmptyTree[A](
// Fill in the rest here...


Assuming a non-balanced tree, for NonEmptyTree's version of add, you only need to consider

1. How would I add a value to a node where left and right are empty?
2. How would I add a value to a node where right is empty?
3. If neither left nor right is empty, on which of those do I call the add method?

Once you have implemented add you can throw away isBST because your tree can't be created invalidly (Well, rather than throw it away entirely, move it into your tests).

Other methods you need to consider implementing:

• contains
• size
• depth (vital for balanced trees)
• delete (rather trickier than add)
• toList
• toSet/toSortedSet
• toString (OK, I know you've done one but it fails if, for example, type A is a string and could contain spaces).

If you add those, you can also make EmptyTree and NonEmptyTree private, further protecting the soundness of your module.

• you have implemented a binary search tree, not a binary tree. Furthermore, even if it is a BST, isValidWith(data < _, left) && isValidWith(data > _, right) is wrong logic. It should be the other way round Jun 2 '16 at 14:48

Just checking (left < this_node < right) is not enough to ensure a valid BST. Consider this tree: 3 < (2 < 1 < 4) < 6. 4 does not belong in the left subtree. Similar example can be made for right subtree.