I am trying to use Scala for my programming language of choice for interviews because it has nice primitives, such as type safety and pattern matching, that offers coders the tools to build elegant and bug-free code, which is what the industry is looking for. I see LeetCode as a platform to help coders hone their skills and help them land very lucrative software engineering jobs. In order to land these jobs, interviewees have to write code that adhere to good standards.

When I was looking at problems to do in LeetCode, particularly the tree problems, I noticed that the binary tree problems are in the form of the following:

 class TreeNode(var _value: Int) {
   var value: Int = _value
   var left: TreeNode = null
   var right: TreeNode = null
 }

This representation of a binary tree is quite bad because it uses null objects. Many companies are trying to avoid the use of null as it quite cumbersome to debug null pointer exceptions. Facebook built a tool called Infer to prevent these type of problems. On top of that, it makes code significantly hard to read as engineers have to account in their heads whether an object is null or not. I've interviewed people who coded in Scala and Java and if they used a null value, my company would automatically disqualify them because there are other alternatives that are better, such as using Options.

There are two data structures that would better represent a Binary Tree as they avoid the usage of null. Here are the structures that I would recommend:

sealed abstract class ADTTreeNode

case class Node(value: Int, left: Tree, right: Tree) extends ADTTreeNode
case object Leaf extends ADTTreeNode

class ClassTreeNode(val _value: Int) {
  var value : Int = _value
  var left : Option[ClassTreeNode] = None
  var right : Option[ClassTreeNode] = None
}

The first alternative gives a more "functional programming" feel than the second alternative as it uses the Abstract Data Type primitive. However, the second alternative is much flexible than first as it users you mutability, which is required for some problems.

Here is how you write a function that converts a binary tree to a list:

object ToListADTTreeNode {
  def to_list(tree : ADTTreeNode) : List[Int] = {
    tree match {
      case Leaf => List()
      case (Node(value, left, right)) =>
        to_list(left) ::: List(value) ::: to_list(right)
    }
  }
}

object ToListClassTreeNode{
  def to_list(tree : Option[ClassTreeNode]) : List[Int] = {
    tree match {
      case None => List()
      case Some(tree) =>
        to_list(tree.left) ::: List(tree.value) ::: to_list(tree.right)
    }
  }
}

Would it be possible to change the Scala binary tree representations that does not use null? I think with this proposed change, it would more people land better jobs. This has a rippling effect as they would refer people to use Leetcode as an interview prep platform, which in hand boost traffic for the website.