Imagine you're working in a massive physical archive of historical documents. If you just threw every paper into a giant pile, finding one specific record from 1922 would take you all day. But if you had a system where you stood at a central desk and the archivist told you, "Everything dated before 1950 is in the left wing of the building, and everything after is in the right wing," you've just cut your search area in half instantly. Once you enter the left wing, you hit another desk that tells you, "Before 1920? Left. After 1920? Right."

That's exactly how a Binary Search Tree (BST) works. It's not just a way to store data; it's a way to organize data so that every time you make a move, you discard half of the remaining possibilities. In Scala, we can implement this beautifully using recursion and algebraic data types.

The Anatomy of a Tree

I've seen a lot of developers try to implement trees in Scala using mutable pointers and while-loops, coming from a Java or C++ background. Don't do that here. The "Scala way" is to define the tree as a recursive data structure. We use a sealed trait to define what a BST is, and then provide two specific cases: an empty tree (the leaf) and a node containing a value and two sub-trees.

sealed trait BST[+A]
case object Empty extends BST[Nothing]
case class Node[A](value: A, left: BST[A], right: BST[A]) extends BST[A]

By using a sealed trait, we're telling the compiler that these are the only two possible shapes a BST can take. This makes our pattern matching exhaustive and safe.

Winding the Path for Insertions

Inserting a value into a BST is like following the directions in that archive. If the tree is empty, you've found your spot. If it's not, you compare your value to the current node's value. Smaller? Go left. Larger? Go right. Since we're staying functional, we don't "modify" the tree; we return a new tree that shares most of its structure with the old one.

def insert[A](tree: BST[A], x: A)(implicit ord: Ordering[A]): BST[A] = {
  tree match {
    case Empty => 
      Node(x, Empty, Empty)
    case Node(v, l, r) =>
      if (ord.lt(x, v)) 
        Node(v, insert(l, x), r) // Rebuild node with updated left branch
      else if (ord.gt(x, v)) 
        Node(v, l, insert(r, x)) // Rebuild node with updated right branch
      else 
        Node(v, l, r) // Value already exists, just return the tree as is
  }
}

Notice the Ordering[A] implicit. I use this because we can't assume A is a number; it could be a String or a custom User object. The Ordering trait gives us a standardized way to handle comparisons.

The Efficiency of the Search

Searching is where the BST really shines. Because we maintained the "left is smaller, right is larger" rule during insertion, we don't have to look at every single element. We just dive down the branches.

def contains[A](tree: BST[A], x: A)(implicit ord: Ordering[A]): Boolean = {
  tree match {
    case Empty => false
    case Node(v, l, r) =>
      if (v == x) true
      else if (ord.lt(x, v)) contains(l, x)
      else contains(r, x)
  }
}

If your tree is "balanced" (meaning it doesn't just look like one long line), this search happens in logarithmic time. In plain English: if you have a million items, you can find your target in about 20 steps. That's a massive win over a standard list.

📋 Practical Task

Implementing a High-Score Registry BST

You are building a leaderboard for a retro arcade game. You need to implement a Binary Search Tree that stores Score objects. A Score consists of a playerName (String) and a points (Int) value.

Your task:

• Define a case class Score(playerName: String, points: Int).
• Implement a custom Ordering[Score] that compares scores based on the points value.
• Using the BST trait and insert/contains logic from the lesson, create a program that:
  1. Inserts three scores: ("Alice", 1200), ("Bob", 800), and ("Charlie", 1500).
  2. Checks if a score of 800 exists in the tree.
  3. Checks if a score of 1000 exists in the tree.